CDR: Re: Minesweeper and defeating modern encryption technology

[Jim Choate]

On Sat, 4 Nov 2000, dmolnar wrote:

> > Another aspect of the N=NP is that the assumption is that if we can
> > resolve a single NP to a P then that should resolve ALL NP to P. That's a
> > pretty big leap with no real analysis behind it. A canon of faith rather
> > than proof or fact.
> 
> I'm sorry. I've been talking about the class "NP" as I've seen it defined
> in class and as in books such as Papadimitriou's _Computational
> Complexity_ or Garey & Johnson's _Computers and Intractability: A Guide
> to NP-Completeness_. This is only partly an appeal to authority; it's
> primarily to clarify what I mean when I'm writing and so try to avoid
> confusion. 
> 
> For the class NP as defined there (and I can give the definition here in a
> separate message if you want, but they do it with more skill and care than
> I would), it is *not* the case that "if we can resolve a single NP to P
> then that should resolve ALL NP to P."
> 
> We *can* identify particular problems for which we can prove
> "if we can solve this problem P in polynomial time, then P = NP." 
> Then P is called an "NP-hard" problem. If the problem P is also itself in
> NP, then P is called an "NP-complete" problem. 
> We can prove these theorems by giving explicit methods to convert a
> solution algorithm for one such problem into a solution algorithm for any
> problem in NP. 

I accept that. A point of clarity, I'm not claiming that N=NP for a single
problem means I can solve all of them. I believe that to say that if a
problem isn't polynomial then it must fit into NP and that ALL NP are
equivalent is just silly. It's like saying N! and be reduced to e^x,
though neither can strictly be reduced to a polynomial.

However, especialy in the press, there seems to be exactly this sort of
view. It seems to be that the impression they leave is that if we find a P
solution to primality we'll as a consequence have a solution avenue to
all other NP problems. It's that 'all other' that I object too. With
respect to your statement above, it just seems they use your wording and
leave the 'particular problems' part out.

    ____________________________________________________________________

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