In sci.math 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?
The Halting Problem is an undecidable problem. That means that there does not exist an algorithm that correctly solves it. The word "intractable" is usually used to describe problems that can be solved, but cannot be solved efficiently. For example, the Travelling Salesman problem can be solved by trying all possible tours and taking the mininum. However this is a very inefficient algorithm and is essentially useless for more than a small number of cities.
> 2) In somewhat layman terms, what exactly is the difference between > NP-Hard and NP-Complete?
A problem is NP-Hard if it is at least as hard as any problem in NP. A problem is NP-Complete if it is NP-Hard and it is in NP.
> 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]
A polynomial time solution for an NP-Hard problem implies P=NP. The fact that NP-Complete problems are NP-Hard is why a polynomial time solution for an NP-complete implies P=NP.
> 4) When we refer to NP, without any qualifiers, does it imply NP-Hard?
No. NP just means that it can be solve in non-deterministic polynomial time. Remember, NP includes all the decision problems that are in P.