On Sat, 4 Nov 2000, Jim Choate wrote:
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.
I was trying to make a distinction between two kinds of problems. I'm sorry if I wasn't clear. 1) The first kind are NP-hard problems. These are problems for which knowing an algorithm to solve the problem *would* allow you to solve every problem in NP. These are the kinds of problems I was referring to in the paragraph I snipped from this message. 2) The second kind are problems which are not known to be in P, which ARE in NP, but which are not known to be NP-hard. Factoring is an example of one such problem. So is discrete log. Knowing a solution algorithm for one of these types of problems does not necessarily tell you anything about solutions for any other problem in NP. These are the kinds of problems I was referring to in "the previous e-mail." I agree with you that the popular press often ignores this distinction, and it's annoying as all get out.
You are in effect saying that primality, travelling salesman, etc. are reducible to a single algorithm with respect to resolution.
It's not a single algorithm, per se. It's a combination of the "reduction" from primality, salesman, etc. to satisfiability + the algorithm for solving SAT. The reduction can be thought of as "reformatting" the problem in terms of SAT; it is specific to each problem. Suppose I have an efficient algorithm FINDSAT(F) which takes a boolean formula F and returns "Y" if it's satisfiable, "N" if it is not. Now my algorithm for factoring looks rougly like this: 1) Run my reduction algorithm from factoring --> SAT. This reduction algorithm is specially tailored to the factoring problem, but one can always be found. Why? 1.1) Because factoring can always be expressed as a program on a nondeterministic TM 1.2) Cook's proof shows how to mechanically express the computation of a nondeterministic TM as a formula which is satisfiable iff the TM halts and accepts on a given string. 2) Take the big weird formula generated from step 1) and feed to FINDSAT(F). You now have a way to solve the problem using FINDSAT(F).
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.
What I would say, according to my understanding of the definitions, is that there is no succint certificate for unsatisfiability known. So the problem of recognizing irresolvable = unsatisfiable formulas is not a problem in NP.
But you're welcome to your own opinion.
As are you, but the hope is that in mathematical matters we can come to some kind of agreement. -David