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