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).
