At 08:42 PM 11/4/00 -0600, Jim Choate wrote:
Hi Bill,
On Sat, 4 Nov 2000, Bill Stewart wrote:
Jim, you're misunderstanding the class NP, though you're correct in not holding your breath.
It's not "all problems that can't be solved in polynomial time." It's "all problems that can be solved in polynomial time by a non-deterministic Turing machine." A non-deterministic Turing machine is allowed to guess answers (or at least, to guess a polynomial number of answers). Answers to NP problems can be verified in polynomial time - the hypothetical machine guesses the answer, and verifies it in a polynomially bounded time.
Which is mathematicaly equivalent to having an algorithm that solves the problem directly in polynomial time.
No - it gives you a direct solution that takes exponential time, because there are exponentially many answers the thing could guess, each of which takes a polynomial time to validate. The "then a miracle occurs" step is that the NTM guesses the _correct_ answer - that's why it's hypothetical, rather than real. The reason that it's interesting mathematics is partly that many NP-complete problems, or NP problems in general, are useful or interesting to mathematicians, and sometimes to real people as well (:-), and that it tells us about the complexity of the problem, and about the difficulty of finding answers, and whether to go for optimal solutions to the problems or to look for heuristics that give pretty good answers most of the time. Thanks! Bill Bill Stewart, bill.stewart@pobox.com PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639