CDR: Re: Minesweeper and defeating modern encryption technology

[Jim Choate]

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.
>  
> The proof is due to Cook (or independently Levin in the USSR). You can
> look it up, or I can try to explain it. If you don't believe it just on my
> assertion here, fine. Please say what you need in order to be convinced.  
> But if you deny that the Cook theorem is proved or take it to mean
> something different, please say so.
>
> You seem to believe that an NP-hardness result is a "pretty big leap with
> no analysis behind it. A canon of faith rather than proof or fact." Why do
> you think this? How does it resolve with the Cook result? Where are
> you getting your definition of NP?

See the last sentence in para 1 above.

You are in fact saying if I can resolve one NP -> P then I can resovle ALL
NP as P. Yet in your earlier email you said the opposite, that you didn't
believe that saying the solution of one NP in a P format meant that all NP
could be solved in a P format.

You are in effect saying that primality, travelling salesman, etc. are
reducible to a single algorithm with respect to resolution.

To word the assertion differently,

"All problems can be reduced to a sum of products such that no single
monomial has a factor more complicated than a power."

I really doubt reality is that simple.

As to Cooks assertion, it is possible to create logical statements which
are irresolvable, irrespective of time or algorithm. So it is clear that
there are in fact statements which can't be resolved so there must be at
least some class of NP that are not resolvable to P.

But you're welcome to your own opinion.

    ____________________________________________________________________

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