On Sat, 4 Nov 2000, Jim Choate wrote: [much material elided - apologies for not going through everything precisely at this time. this point particularly struck me.]
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. 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? Is every problem in NP NP-complete? Now, if P = NP, then every single problem in NP is "NP-hard" trivially. Because we can solve them ALL in polynomial time. But if P != NP, then the question "are all problems in NP NP-hard?" becomes interesting. Not every problem in NP is known to be NP-hard, however. For instance, factoring is not known to be NP-hard. If factoring is found to be polynomial time, then P ?= NP is still open. We seem to have different definitions of "the class NP" at work here, and so we're going to talk past each other until this is resolved. Is it clear to you what I'm using now? if not, what more do you need? Thanks, -David