
Re: On NP Completeness and Intractability
Posted:
Oct 27, 2005 6:09 PM


In article <djr3og$1mr$1@joe.rice.edu>, Randy <joe@burgershack.com> wrote: >With each mention of NP or NPC in the various research >papers I've read, I have never seen subsequent statements grounding the >implications of the problem as being specifically and formally NPHard >or NPC, beyond merely being exponential or infeasible or unpredictable.
I've certainly observed this too. It is usually true that simply proving NPcompleteness is of not much practical use. It would be better to ask followup questions, e.g., look at the proof of NPcompleteness. Was the reduction from a problem with a polynomialtime approximation scheme, or at least a constantfactor approximation algorithm, and does the reduction preserve approximability? If so, then you automatically have a polynomial time algorithm with an a priori performance guarantee. If the reduction doesn't preserve approximability, do at least the heuristic methods carry over? Another question to ask is, is the problem fixedparameter tractable for a suitable choice of parameter? That would give you a good clue as to the regime in which problem instances might be tractable in practice.
Unfortunately, understanding these additional questions, and trying to answer them, takes a lot of work, and most people (or their bosses) are too impatient.  Tim Chow tchowatalumdotmitdotedu The range of our projectileseven ... the artilleryhowever great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. Galileo, Dialogues Concerning Two New Sciences

