CDR: Re: Minesweeper and defeating modern encryption technology
Jim Choate
ravage at ssz.com
Sat Nov 4 09:02:38 PST 2000
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 --'-
--------------------------------------------------------------------
More information about the Testlist
mailing list