CDR: Re: Minesweeper and defeating modern encryption technology
Jim Choate
ravage at ssz.com
Sat Nov 4 15:10:07 PST 2000
On Sat, 4 Nov 2000, dmolnar wrote:
> The original problem for which this was shown was formula satisfiability:
> "given a boolean formula, does there exist an assignment to all of its
> variables which makes the formula evaluate to true?"
> If you can solve formula satisfiability in polynomial time, you can solve
> any NP problem in polynomial time.
Which we now know to be impossible given Godels Incompleteness Theorem,
it's also a form of Turings Halting Problem.
It should be worded something like:
"given SOME boolean formula,..."
____________________________________________________________________
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