CDR: Re: Minesweeper and defeating modern encryption technology

Jim Choate ravage at ssz.com
Sat Nov 4 18:42:07 PST 2000


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. One only has to add to the solution
time the factor that represents the 'walk time'. Let's consider a prime
seive. The numbers are the positive integers and they're a line. So we
take the time to check the solution for any given guess and add to it an
'mx+b' factor to represent the time to generate your guesses (in this
cases the positive integers).

Last time I checked a polynomial plus a polynomial was just another
polynomial. We're not talking about absolute magnitudes but rather the
relative magnitude differences of the algorithms.

How one pronounces 'tomato' isn't relevant.

In fact, it is clear that if the algorithm necessary to generate your
'guess' is itself non-polynomial then you've demonstrated the sum (i.e.
time to generate guess plus time to check) can't itself be polynomial. In
the case where a random number is used to generate a guess then the factor
is a simple constant (i.e. '+c') added to the solution time. Iterations by
constant value will also consist of the 'loop time' to execute the sum,
again a simple constant. So, in most cases the effort needed to generate
the guess or walk sequentaly through a state space or through a random
proceess is inconsequencial.

    ____________________________________________________________________

                     He is able who thinks he is able.

                                           Buddha

       The Armadillo Group       ,::////;::-.          James Choate
       Austin, Tx               /:'///// ``::>/|/      ravage at ssz.com
       www.ssz.com            .',  ||||    `/( e\      512-451-7087
                           -====~~mm-'`-```-mm --'-
    --------------------------------------------------------------------





More information about the cypherpunks-legacy mailing list