email@example.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 > NP-Hard and NP-Complete? > 3) If a polynomial time algorithm is discovered for a hitherto NP-Hard > 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 NP-Complete problem, then P=NP] > 4) When we refer to NP, without any qualifiers, does it imply NP-Hard?
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 co-NP 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 co-NP iff its opposite, e.g. is X composite or 1, is in NP.
NP-complete and NP-hard are usually used as adjectives, e.g. SAT is NP-complete. The class of NP-complete problems is sometimes called NPC. I've never seen NPH.
A problem is NP-complete 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 co-NP in polynomial time.
An NP-hard problem is at least as hard as every problem in NP. Another poster said that an NP-hard problem need not be a decision problem. An NP-hard 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 co-NP.