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@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------