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?