7 ms·

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 the

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.

DoctorOetker 8y ago
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?
- ColinWright 8y ago
  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.
  - DoctorOetker 8y ago
    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
    - ColinWright 8y ago
      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.
      - DoctorOetker 8y ago
        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.

DoctorOetker 8y ago

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?

ColinWright 8y ago
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.
- DoctorOetker 8y ago
  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
  - ColinWright 8y ago
    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.
    - DoctorOetker 8y ago
      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.