
Re: On NP Completeness and Intractability
Posted:
Oct 25, 2005 4:12 PM


nimmi_srivastav@yahoo.com wrote: > 1) All the literature pertaining to intractability that I have seen > refers to the Turing's Halting Problem. What are other common examples > of intractable problems? > 2) In somewhat layman terms, what exactly is the difference between > NPHard and NPComplete? > 3) If a polynomial time algorithm is discovered for a hitherto NPHard > problem, does that have any implication for the P=NP question? > [I already know that if a polynomial time algorithm is discovered for a > hitherto NPComplete problem, then P=NP] > 4) When we refer to NP, without any qualifiers, does it imply NPHard?
The Halting problem is undecidable. The means that there is no algorithm that will solve it.
The P of decision problem classes P, NP, and coNP refers to polynomial time.
A decision problem, e.g., does integer X divide integer Y, is in P iff it can be solved in polynomial time.
A decision problem, e.g. is X composite, is in NP iff for instances where the answer is yes the answer can be verified in polynomial time with a lucky guess, e.g a factor of X.
A decision problem, e.g. is X prime, is in coNP iff its opposite, e.g. is X composite or 1, is in NP.
NPcomplete and NPhard are usually used as adjectives, e.g. SAT is NPcomplete. The class of NPcomplete problems is sometimes called NPC. I've never seen NPH.
A problem is NPcomplete iff any problem in NP can be converted to it in polynomial time. That is the mechanism by which finding a polynomial algorithm for NPC would allow solving all of NP and coNP in polynomial time.
An NPhard problem is at least as hard as every problem in NP. Another poster said that an NPhard problem need not be a decision problem. An NPhard decision problem need not be in NP, but it must be decidable.
There are other classifications of decision problems. E.g. PSPACE is the class of decision problems whose solution requires a only polynomial amount of memory. It includes decidable problems that are in neither NP nor coNP.

