<p>what Papadimitriou and Yannakakis mean is something along the following lines. Consider the language L consisting of all triples &lt;M,x,t&gt; where M is a nondeterministic Turing machine, x is a string, and t is another string, such that M on input x has an accepting run of at most |t| steps (|t| denotes the length of t). Clearly, L is NP-complete, or, if you want, &quot;universal for NP&quot;. Now Cook's proof contains all the ideas to show that L can be reduced to SAT in polynomial time. Thus, SAT is NP-complete as well.</p>

CC BY-SA 4.0
2022-08-25T20:23:06.310Z
2022-08-25T20:23:06.310Z
vdbuss
<p>From Papadimitriou and Yannakakis, &quot;A Note on Succinct Representations of Graphs&quot; second parragraph of the proof of the main result.</p>
<blockquote>
<p>Cook (1971) presented in his classical paper a construction whereby, given a string x, we can construct in polynomial time a Boolean formula, such that the formula is satisfiable if and only if a particular machine, universal for NP, accepts input x.</p>
</blockquote>
<p>I do not see in Cook's &quot;The Complexity of Theorem-Proving procedures&quot; (read from <a href="https://www.inf.unibz.it/%7Ecalvanese/teaching/11-12-tc/material/cook-1971-NP-completeness-of-SAT.pdf" rel="nofollow noreferrer">here</a>) the construction of such universal machine. To be explicit:</p>
<ul>
<li>what is a universal machine for NP?</li>
<li>how does Cook's theorem 1 in the quoted paper show that NP has a universal machine?</li>
</ul>

CC BY-SA 4.0
2022-08-23T21:24:10.233Z
The paper of Cook in question is https://doi.org/10.1145/800157.805047.  The abstract: *"It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a tautology...."*  Surely this is the paper in which Cook showed that SAT is NP-complete, by showing how to reduce an arbitrary NP problem to SAT.  Looking at the paper you link to, the reduction (which is what you seek) is in the proof of Theorem 1.  Note that there "DNF tautologies" is the complement of SAT.
Neal Young
CC BY-SA 4.0
2022-08-24T03:44:58.047Z
What does it mean by a machine that is "universal for NP"? (maybe this is part of your question)
usul
CC BY-SA 4.0
2022-08-24T04:38:57.117Z
I don't see a question here.  This is a question-and-answer site, so we require you to articulate specific question.  We also require you to provide proper attribution for all quotes (https://cstheory.stackexchange.com/help/referencing) and to show your efforts (see our [help/on-topic]).
D.W.
CC BY-SA 4.0
2022-08-24T08:32:53.207Z
@usul indeed, that is my question, what's a universal machine for NP and how does Cook's theorem 1 show that NP has one
user1868607
<cc.complexity-theory><np-complete><np><universal-turing-machines>
Cook's theorem and universal machine
user1868607
# Cook's theorem and universal machine

(Asked by: username_0 on 2022-08-23)

From Papadimitriou and Yannakakis, "A Note on Succinct Representations of Graphs" second parragraph of the proof of the main result.

> Cook (1971) presented in his classical paper a construction whereby, given a string x, we can construct in polynomial time a Boolean formula, such that the formula is satisfiable if and only if a particular machine, universal for NP, accepts input x.

I do not see in Cook's "The Complexity of Theorem-Proving procedures" (read from [here](https://www.inf.unibz.it/%7Ecalvanese/teaching/11-12-tc/material/cook-1971-NP-completeness-of-SAT.pdf)) the construction of such universal machine. To be explicit:

* what is a universal machine for NP?
* how does Cook's theorem 1 in the quoted paper show that NP has a universal machine?

**Tags:** cc.complexity-theory, np-complete, np, universal-turing-machines

> **Comments:**
> **username_1**: The paper of Cook in question is https://doi.org/10.1145/800157.805047.  The abstract: *"It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a tautology...."*  Surely this is the paper in which Cook showed that SAT is NP-complete, by showing how to reduce an arbitrary NP problem to SAT.  Looking at the paper you link to, the reduction (which is what you seek) is in the proof of Theorem 1.  Note that there "DNF tautologies" is the complement of SAT.  
> **username_2**: What does it mean by a machine that is "universal for NP"? (maybe this is part of your question)  
> **username_3**: I don't see a question here.  This is a question-and-answer site, so we require you to articulate specific question.  We also require you to provide proper attribution for all quotes (https://cstheory.stackexchange.com/help/referencing) and to show your efforts (see our [help/on-topic]).  
> **username_0**: @username_2 indeed, that is my question, what's a universal machine for NP and how does Cook's theorem 1 show that NP has one  

---

## 1 answers

### Answer by username_4 on 2022-08-25. Score: 2 | Accepted answer

what Papadimitriou and Yannakakis mean is something along the following lines. Consider the language L consisting of all triples  where M is a nondeterministic Turing machine, x is a string, and t is another string, such that M on input x has an accepting run of at most |t| steps (|t| denotes the length of t). Clearly, L is NP-complete, or, if you want, "universal for NP". Now Cook's proof contains all the ideas to show that L can be reduced to SAT in polynomial time. Thus, SAT is NP-complete as well.


---

