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