CDR: Re: Minesweeper and defeating modern encryption technology

[Bill Stewart]

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 at pobox.com
PGP Fingerprint D454 E202 CBC8 40BF  3C85 B884 0ABE 4639