CDR: Re: Minesweeper and defeating modern encryption technology

Bill Stewart bill.stewart at pobox.com
Sat Nov 4 16:35:34 PST 2000


At 11:02 AM 11/4/00 -0600, Jim Choate wrote:
>On Sat, 4 Nov 2000, Declan McCullagh wrote:
>> "NP" problems, on the other hand, are those that can be solved in
>> nondeterministic polynomial time (think only by guessing). NP includes P.
>
>Actualy any time that can't be described using a polynomial (i.e. a0 +
>a1x + a2x^2 + ...) is NP. For example something that executes in factorial
>or exponential time is NP.
>
>If it is found that all NP can be reduced to P then I'd expect to see
>somebody be able to express a factorial (for example) as a polynomial.
>I ain't holding my breath.
>
>The 'nondeterministic' part simply means it's unknown if the problem can
>be reduced to a polynomial representation.
>
>As to 'guessing', some processes are polynomial and some aren't.

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.

There are lots of problems that are outside of NP - they're known
to take exponential amounts of time to solve, regardless of whether
you've got a NTM which can pull correct bits out of /dev/oracle.
There are also lots of problems for which the complexity is unknown,
such as factoring.  Until ~20 years ago, linear programming was
believed to be part of NP, but Karmarkar's algorithm (which I think
was based on Shor's work?) demonstrated a way to solve it in polynomial time,
though with an annoyingly large polynomial.

NP-complete problems are a certain set of problems for which it can
be proven that if you can solve one problem in that set in polynomial time,
you can use only polynomially more work to solve any other problem in that
set.
Usually people reduce things to the Satisfiability problem,
though sometimes others are more convenient.

When I was studying complexity theory from Karp back in grad school,
one thing I didn't understand was the issue of whether there might be
other sets of problems that are similarly hard but not reducable to 
each other, e.g. a set NP1 of hard problems including satistiability,
Hamiltonian paths, etc., a set NP2 of hard problems including Foo and Bar
that are reducable to each other but haven't been proven to
solve or be solved by NP1 (or at least not both.)
Perhaps it's a definitional thing, or perhaps there are proofs that
were beyond the scope of a first-year grad course, or perhaps
the problems that appear to be that hard just keep turning out
to be members of the well-known NP-complete set, or perhaps
there was something obvious I was just missing...
				Thanks! 
					Bill
Bill Stewart, bill.stewart at pobox.com
PGP Fingerprint D454 E202 CBC8 40BF  3C85 B884 0ABE 4639





More information about the cypherpunks-legacy mailing list