CDR: Re: Minesweeper and defeating modern encryption technology

[Jim Choate]

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.

    ____________________________________________________________________

                     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 --'-
    --------------------------------------------------------------------