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?
This is more than intractable. The halting problem is recursively unsolvable. Also the equivalence problem, i.e. show that two Turing machines halt on the the same inputs and produce the same results.