Cook’s Paper
Here is a nice pdf version of the famous paper by Steve Cook. Thanks to Tim Rohls.
7 Comments
leave one →
a personal view of the theory of computation
Subscribe to Gödel’s Lost Letter
Our Book
Click image for our page, with errata and links.
Recent Comments
Jordan on An Open Problem Jon Awbrey on An Open Problem Blog Runner on An Open Problem William Gasarch on An Open Problem DL on An Open Problem Jon Awbrey on An Open Problem An Open Problem | Gö… on Cargo Cult Redo Peter Gerdes on Women in Math Research Peter Gerdes on Women in Math Research rjlipton on Women in Math Research Cristóbal Camarero on Women in Math Research Yasu on A Big Result On Graph Isomorph… Yuly Shipilevsky on Guggenheim 2024 Blog Runner on 2023 Turing Award Blog Runner on Guggenheim 2024 Sitemeter
The quest for a formula for nonpolynomial time is linked with abstraction logic theory IFF one takes the writings of the SilverProfessor KitFine OxonPress seriously. He states that
the most genuine of abstraction datums has to be a domain which is both Universal and restricted in its range. Also nb HandbookOfPhilOFMathsandLogic
I have found out the recent claimrePnotequaltoNP interesting. Ienjoyed solving the Cook number puzzle onWIKI re -2-3+15-10+7+14 on a topological basis to agree with the SilverProfessor suggestion in his official book It was a transitional datum I chose to establish after hard work the bisynthesis ie there are two ways one can prepare an impartial code to replace any set of numbers by another. One is complicated and requires the discovery of the Graft ie the oracle as you call it. The other is more formal and one can play
‘hotel rooms’with thes et of numbers. That is one has to add pairs from both the given and the devised set to check which pairs add the same So eventually you see the subset zero coincidentally isolated. However the other synthesis based ona concept of the restricted range dpoes not help like this It is disasterous There is no link at all with the WIKI set given So one has to use the Graft. It is still a computor hence Boolean programmable even though it is a requirement what the computor has to recoolect to say YES or NO. I have therefore proved that the datum is transitional. I only just found out that the papers by Cook do outline this would be so. OKAY THEN there is still the question what you regard is a sensible datum for the identity called recursive time.
I have today found a function which does away with the excessive computational work I admitted I got into. It is a function which permits one to express the output of a set whhich contaiins a possible sub-set zero so that the output is a near perfect demarcation. I tested it on the WIKI set example and others invented much more awkward to notice that this question by Cook about a function is to be found. After so much indirect work due to the
interest in Clay Inst 2003 book on trace harmonics etc I feel now that this is better than
the excessive computational work. I am able to understand why this works and that the mainline attempts require heavy logic. One of the sets invented for the purposes was allprimes and it was under 100 ea of 7terms. The function showed a difference with what I knew about the set. I cannot explain this formally because it was a two against two to zero in 7 terms which is high ratio for a zero sub-set. I knew something about one of the primes and left it out;adjusted the input to get another answer.This was now 1.85percent off the knowable balance for ewach of the two terms. I am wondering about the RH now;it must have some connection if you say so. So I am bound to write logic again I suppose. This Length is related to transitional appreciation. I hope friends of Cook reading this will be able to confirm his position is now the same and we have to share the logic papers re RH length I dont understand the need for a sequence at all. The sets can be presented any order to use this function re a RunTime hazard function as I call it. The difference within this particular set of primes to bal appears to have a connection with the N factors of a prime multiple which employs this particular prime It has few multiples within the special view that certain prime multiples are not acceptable for theoretical reasons. I have got to explain this sometime. They dont zero within themselves. Its cranky to most folk but I have tested statistically and its too hard for anyone generally without being involved with it. Clay says I should approach a aUniv and get a shared reln re these matters I am in UK and Oxon is not on the same thing.
One thing I don’t understand about Cook’s result, following Garey and Johnson’s version:
Seems like it would be incorrect to claim that “if SAT can be solved in P-time, then every problem in NP can also be solved in P-time”. Why? Because Cook’s proof is an “existential” proof — not a “constructive” proof.
I’m following Sections 2.3–2.6 of Garey and Johnson.
His NDTM consists of a guessing phase where it guesses a string $w$, followed by a deterministic checking phase — both phases are done in poly time, of course. (The input to the NDTM is a string $x$.)
As an existential proof, that any language L in NP will reduce to SAT, the proof in Sec. 2.6 is fine — if $x \in L$, then there MUST exist a correct guess $w$, followed by a polynomial time computation which accepts $x$. I agree with this.
However in a constructive sense…
You have only “guessed” the initial string $w$ at the beginning of the reduction to SAT. Your guess may be good, or it may NOT be. To correctly solve L in poly time, even using the reduction to SAT, your guess $w$ should have been a good (or correct, appropriate) guess — and the correct guessing should also have been accomplished in poly time.
Suppose $x \in L$, but the guess $w$ is bad — Then the expression obtained for SAT is meaningless, the answer obtained for SAT is meaningless, then there is no way to recover the correct answer for L (that $x$ is indeed a member of L)…. you have to keep trying till you guess $w$ correctly (so that you get a meaningful SAT expression).
If SAT can be solved in poly time, it does NOT mean that every problem L in NP can be solved in poly time.
You might ask, “If I can guess $w$ correctly for every $x$, then who needs the reduction to SAT?” …. hmmm, this seems to be an irony.
So in a constructive sense, it looks like Cook’s proof fails. No way that L can be solved deterministically in poly time.
Can anyone please explain this?
An important question for classes. When I teach I try to take the element of “guessing” out and instead emphasize the definition of NP in terms of relations R(x,y) that are decidable in time polynomial in |x|. The point is that any question about the existence of a y gets effectively transformed into a question about the existence of a satisfying assignment z for a certain formula f. Not only does an algorithm solving the latter yield an algorithm for whether there is a y, the textbook versions of Cook’s Theorem (following Karp or Levin or C.P. Schnorr) make it so that y is directly obtainable from z (which was Levin’s point; also x is obtainable from f).
Thank you for the pointer to Levin’s reduction (assuming that it can be called so). I’ll look it up soon.
But my argument about Cook’s reduction still holds. Doesn’t matter whether you guess an initial string, or make random moves at each transition of the NDTM. As a technique/tool to decide an arbitrary language L in NP in Detr Ptime using a Ptime Detr algorithm for SAT, Cook’s reduction will fail.
Assume that an input $x$ is a member of the language L. Also assume that you have designed an NDTM called M to decide L. You start running M on input $x$. Suppose at the fifth transition, M non-deterministically chooses a bad move — hence M is going to stop (crash) at a non-accepting state. So the resulting expression for SAT is garbage, the resulting solution for SAT is garbage — and hence the resulting answer to the question “Is $x$ a member of L?” will also be garbage.
I don’t know whether Levin’s reduction will work — if an equivalence between Cook’s reduction and Levin’s reduction has been shown, then the latter wouldn’t work either.
Once you start running M on $x$, you are asking for trouble since M is non-det.
The M-crashing would correspond to a particular unsatisfying assignment, from which the non-crashing could be traced back. That is true of both Cook and Levin’s reductions. But running M on x is not the point—the point is the existential quantification over nondet. choices and over assignments.
Pip is correct.
To Existential Proof — Of course you do NOT actually let M run 🙂 If you do that, at some point M could make a bad move (as you point out yourself). Instead, for every time step, just encode all possible moves with an OR expression (disjunction), and then let the SAT algorithm take care of the rest.
The number of possible moves at each step is equal to the number of “arcs” or “transitions” in the diagram for M — may be a large number, but still a constant for every M. The SAT assignment will pick exactly one of these moves for each time step.
Everything else is just book keeping.