CDR: Re: Minesweeper and defeating modern encryption technology

dmolnar dmolnar at hcs.harvard.edu
Sat Nov 4 11:20:01 PST 2000



On Sat, 4 Nov 2000, 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.

I'm sorry - by the definitions I know, Declan has it closer.
I'm not sure what you're getting at with "any time that can't be
described..." or "something that executes in factorial or exponential
time." As far as I know, NP is a class of *problems*, not a
class of running times or even a class of algorithms.

It doesn't make sense to say "x^2 is in NP", strictly speaking. 
It doesn't make sense to say "Ford-Fulkerson is in NP", strictly speaking. 
It makes more sense to say "primality testing" is in NP, if that
refers to the problem of "Given a number n, is n prime?" 

NP can be defined as the class of problems for which there exist "succint
certificates". That is, given a problem instance, there is some string S
which

	a) is "succint" - its size is bounded by some polynomial in the
	size of the problem instance,

	b) can be verified as a "real" solution to the problem in
	polynomial time. i.e. the solution has a "certificate" which
        will convince you beyond doubt that this really is a solution.

By the way, I don't recall if anyone's defined polynomial time yet in this
thread. "Polynomial time" means that a computer will take a number of
"steps" bounded by some polynomial which takes as parameter the length
of the problem instance. Here "steps" mean what you think they mean;
pinning them down precisely requires specifying your model of computation
precisely, which can be time-consuming. 

NP is the class of all problems for which these "succint certificates"
exist. Once you've found an answer, you can check it easily. But you
are *not* guaranteed anything about finding the answer. Finding the answer
might be "hard." 

This is one way of thinking about NP. Declan seems to have in mind
an alternative (but equivalent) definition, in which we consider NP 
as the class of problems solvable by machines which have the magic
ability to always know the "right" way to go at every branch point
of a computation. This is another way to think about it; I personally
prefer the "succint certificate" definition. 

Then P is the subset of NP -- problems for which finding the certificate
is "easy."  That is, there is a polynomial-time algorithm for finding a
solution to the problem in the form of one of these "succint
certificates." The P vs NP question is then whether P is a proper 
subset - i.e. is there some problem in NP but not in P?

Factoring in in NP. A succint certificate that you've factored a number
n are its factors, because you can just multiply them together to check.
Finding the factors is another thing entirely...

There are many more isssues here, of course. One such issue is the average
case hardness of a problem. In the case of RSA, we actually have that RSA
is "randomly self-reducible" -- the ability to solve even a small fraction
of instances (say 1%) of all RSA instances would imply the ability to
solve every RSA instance. This gives some evidence that RSA is "uniformly
hard." But this is not known for many other problems in NP, for which
the average case complexity is unclear. 

More fun on that subject may be found at Russell Impagliazzo's page
http://www-cse.ucsd.edu/users/russell/

in the paper "A Personal View of Average Case Complexity." 

-David





More information about the cypherpunks-legacy mailing list