In article <firstname.lastname@example.org>, Randy <email@example.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 NP-Hard >or NPC, beyond merely being exponential or infeasible or unpredictable.
I've certainly observed this too. It is usually true that simply proving NP-completeness is of not much practical use. It would be better to ask followup questions, e.g., look at the proof of NP-completeness. Was the reduction from a problem with a polynomial-time approximation scheme, or at least a constant-factor 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 fixed-parameter 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 tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however 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