Not necessarily. You specify the objective, just as you do with compile-time optimization. You can LTO with binary size objective, -Os or -Oz, or for speed, -O/2/3 whatever.
Nit: if number n is given in binary representation in the input, then an O(n)-algorithm runs in exponential time as n is an exponential function of log(n). Hence, log(n)^O(1)-time algorithms for the Fibonacci number are reasonable to exist, unless the decision version of the Fibonacci number is NP-hard.
Well, it always depends on what you lookup i.e. how much time one needs to compute entries of the given lookup table. If it takes O(2^n) time , then payback comes quickly, where n is the input size. It’s good advice to be very skeptical if one drops general statements like that. Look for algorithms with the best worst -case time complexity is a good start. It will always win. Theory works. Question is only of big the input has to be in order to see that. Here, the fun part starts I guess.
if a problem is NP-hard does not mean that each instance is hard to solve. From my experience many instances appearing in practice are easy to solve even if there very large. The problem with these instances is that it takes to much space to write done the SAT-formual. So you do not even get to the point where you would run the solver. But a simple problem specific search tree algorithm has no problem with solving it. Bottom line, if you really need to solve a NP-hard problem then you might want to look for fixed-parameter tractable algorithms.
Given 2 NP-hard problems and a transformation that translates (in polynomial time) any instance of NP-hard problem type 1 into an instance of NP-hard problem type 2, and if type 1 has a known fixed parameter tractable algorithm, can we "translate" the fixed parameter from type 1 to an equiproblematic parameter in type 2?
That's not the point (as I understand it). The point is that many instances of NP-Hard problems are, in truth, easily solved.
To give an accessible example, consider the problem of finding a factor of an integer. I know this isn't NP-Hard, but it's something most people can easily think about.
If you choose a random large integer, odds are it has a small factor. 50% of the time it's divisible by 2, and most numbers (in a very real sense) or divisible by 2, 3, 5, or 7.
So most of the time a randomly chosen number is easy to find a factor of. In a similar way, most real-world instances of NP-Hard problems are actually easy to find a solution for. The proportion of difficult instances shrinks as the instance size increases[0]. Specifically, if you have an instance of SAT generated from a real-world situation, the likelihood is that it's not actually that hard, so even if it's large, an off-the-shelf SAT solver might be able to dash off a solution.
So when confronted by an NP-Hard problem don't just instantly give up. Choose an algorithm that has a go, and there's a good chance you'll get a solution.
[0] There are formal, unproven conjectures about this.
Yes I understood this, but thanks for making sure anyway...
That still does not answer my question. I see and understand the utility of fixed parameter tractability.
This naturally made me wonder about the proofs that a certain problem type P' is NP-hard (by being able to transform problem from P' to known NP-hard problem P and back): can these translations be used to deduce the relevant fixed parameter for NP-hard problems if one of the 2 problem types (P' or P) has a known fixed parameter tractable algorithm...
I.e. you did not answer my question at all, you just reiterated basic complexity theory
OK, then I don't understand your question. I'm not an expert, so perhaps I'm not in a position to understand, let alone answer, but it's worth clarifying in case someone else can step in.
Suppose we have two problems, A and B. We have polynomial time transforms between them, so they are considered "equally difficult".
In reading and re-reading the thread it appears that you (pl) are talking about having a "fixed parameter tractable algorithm" for one of the problems, say problem A, and you (sng) are asking if the transform then provides an equivalent fixed parameter tractable algorithm for B.
If that's the case then I don't know enough to answer, but my feeling is "probably not in general".
If that's not what you're asking then you might like to be more specific.
In either case I suspect I can't add anything useful.
Your last comment indicates you do understand my question! so I upvote it :)
Not sure what you mean with pl and sng in "you (pl)" and "you (sng)"
Most fantastic would of course be a general method so that given as inputs the transforms between problem types, and the known fixed parameter, and fixed parameter tractable algorithm, gives as output the new fixed parameter, and a new fixed parameter tractable algorithm for the new fixed parameter.
I assume we do not have such a general method, so similarily interesting would be data points for constructing such a method: examples of deducing the fixed parameter for a problem domain, given the fixed parameter (and tractable algorithm) from those of a different problem type.
With enough examples perhaps a general method can be guessed.
> Your last comment indicates you do understand my question! so I upvote it :)
OK, cool, thanks!
> Not sure what you mean with pl and sng in "you (pl)" and "you (sng)"*
"Plural" and "Singular" - in English I can't make it clear that in some cases I'm talking about you and previous speakers, and in other cases I'm talking only about you. Other languages make it easier to make the distinction, in English it must be inferred, or made explicit.
> Most fantastic would of course be a general method so that given as inputs the transforms between problem types, and the known fixed parameter, and fixed parameter tractable algorithm, gives as output the new fixed parameter, and a new fixed parameter tractable algorithm for the new fixed parameter.
I feel like that's a lot to ask, but we are beyond my expertise.
> I assume we do not have such a general method ... With enough examples perhaps a general method can be guessed.
I have no intuition about this at all, so I'll stand aside and let others with greater knowledge comment, if they're around.
Okay let (P,k) be a parameterized problem which admits a fixed-parameter algorithm with respect to k.
That means you have an algorithm which runs in f(k)n time, where n is the input size and f is a function only depending on k (for example (2^k)*n). Hence, if your real-world instances have always a small k then you can solve arbitrary large instances. Note that one problem can have a lot of different parameters and not all admitting such an algorithm (unless the world is very different than we believe). Now let (P’,h) be another parameterized problem and you have a polynomial time reduction from P’ to P. Then, this reduction gives you a fixed-parameter algorithm for P’ with respect to h if the value of k in the reductions depends only on h and nothing else.
There's no general answer to your question, it depends on the problems. You can find parameter-preserving reductions between some problems, but this isn't always the case.
Also, instead of looking at fixed parameter tractability, it often makes more sense to look at approximation algorithms (if your goal is to optimize something, rather than getting a strict Yes/No answer).
It looks like they understand memory as a tree, but in complex structures it's a graph. I couldn't found how they handle ring topologies. I guess, this stealing stuff doesn't help.
IIRC, talloc basically doesn't handle rings. Note, however, that it's fairly easy to create a "reference to the entire ring" that cleans up some node/the entire ring when it's deallocated, or to explicitly deallocate some node of the ring.
For what it's worth, non-tree reference graphs are a lot rarer than you'd think. (Note, for instance, that Perl doesn't clean them up automatically except in a few specific cases; this is annoying, but Perl is clearly usable!)
It would be nice to justify statements. To write something in upper cases isn't a justification and doesn't make sense.
Each new programming language seems to be better and so on. But if we are looking to the hottest shit on the planet of the past year like java, ruby, python, etc. we can say that we didn't know their problems at the beginning.
