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