<p>There are <em>two</em> results this could plausibly be which nicely contrast each other - they differ on whether we look at finite or infinite structures:</p>
<ul>
<li><p><strong>(<a href="https://en.wikipedia.org/wiki/Entscheidungsproblem" rel="nofollow noreferrer">Turing</a>, following <a href="https://en.wikipedia.org/wiki/G%C3%B6del%27s_completeness_theorem" rel="nofollow noreferrer">Godel</a>)</strong> The <strong><em>validity</em> problem for first-order logic on <em>arbitrary</em> structures</strong> in a sufficiently rich language is <span class="math-container">$\Sigma^0_1$</span>-complete; for example, the set of (codes of) sentences true in every directed graph is <span class="math-container">$\Sigma^0_1$</span>-complete.</p>
</li>
<li><p><strong>(<a href="https://en.wikipedia.org/wiki/Trakhtenbrot%27s_theorem" rel="nofollow noreferrer">Trakhtenbrot</a>)</strong> The <strong><em>satisfiability</em> problem for first-order logic on <em>finite</em> structures</strong> in a sufficiently rich language is <span class="math-container">$\Sigma^0_1$</span>-complete; for example, the set of (codes of) sentences true in some finite directed graph is <span class="math-container">$\Sigma^0_1$</span>-complete.</p>
</li>
</ul>

CC BY-SA 4.0
2021-10-10T23:44:28.497Z
Since this is often overlooked, let me observe that by far the most surprising part of either of these results is the upper bound on the validity problem for arbitrary structures, which at first glance is merely $\Pi_1$ in the [Levy hierarchy](https://en.wikipedia.org/wiki/L%C3%A9vy_hierarchy); see the discussion [here](https://math.stackexchange.com/questions/2099531/how-to-verify-satisfialibility-in-a-model-confusions-with-g%C3%B6dels-completeness).
Noah Schweber
CC BY-SA 4.0
2021-10-10T23:42:49.680Z
2021-10-10T23:42:49.680Z
Noah Schweber
<p>An academic descendant of Cook just lectured on NP completeness. He said that the idea came from a well-known theorem in first-order logic that talks about completeness of satisfiability for computably enumerable languages. He didn't seem to know exactly which.</p>
<p>Do we know what the theorem is? I bet is not mentioned in the original paper.</p>
<p><strong>Update</strong></p>
<p><a href="https://www.youtube.com/watch?v=M_S_pbaMy0o" rel="nofollow noreferrer">Here</a> is Stephen Cook himself explaining.</p>
<ul>
<li>Completeness for recursively enumerable sets.</li>
<li>Unsatisfiable predicate calculus formulas are complete for recursively enumerable problems.</li>
<li>Why can't we do this for propositional formulas?</li>
<li>Analog of recursively enumerable becomes NP.</li>
<li>The reductions he used were Turing reductions not Karp's.</li>
</ul>

CC BY-SA 4.0
2021-10-04T20:23:26.527Z
The closes result I know is that the satisfiability problem of first-order logic over finite structures is $\Sigma_1^0$-complete, i.e., complete for the class of computably enumerable languages.
Reijo Jaakkola
CC BY-SA 4.0
2021-10-04T20:55:09.610Z
Not judging the validity of the original claim, but a  "well-known theorem" which even the speaker "didn't seem to know exactly" seems to be stretching the definition of "well-known" a little.
Clement C.
CC BY-SA 4.0
2021-10-04T22:19:52.300Z
@ReijoJaakkola that helps. It sounds likely that was the result I will confirm. What is a standard reference for that kind of result?
user1868607
CC BY-SA 4.0
2021-10-05T06:21:28.603Z
I googled **history of NP completeness** and found [this publication by David Johnson](https://www.math.uni-bielefeld.de/documenta/vol-ismp/50_johnson-david.pdf).
Shuxue Jiaoshou
CC BY-SA 4.0
2021-10-12T07:31:20.397Z
https://www.youtube.com/watch?v=M_S_pbaMy0o 1:09
user1868607
CC BY-SA 4.0
2021-10-25T12:31:58.620Z
The notion is defined in his lecture notes http://www.cs.toronto.edu/~sacook/csc438h/
user1868607
<cc.complexity-theory><np-complete><cook-levin>
Cook inspiration for NP completeness
user1868607
# Cook inspiration for NP completeness

(Asked by: username_0 on 2021-10-04)

An academic descendant of Cook just lectured on NP completeness. He said that the idea came from a well-known theorem in first-order logic that talks about completeness of satisfiability for computably enumerable languages. He didn't seem to know exactly which.

Do we know what the theorem is? I bet is not mentioned in the original paper.

**Update**

[Here](https://www.youtube.com/watch?v=M_S_pbaMy0o) is Stephen Cook himself explaining.

* Completeness for recursively enumerable sets.
* Unsatisfiable predicate calculus formulas are complete for recursively enumerable problems.
* Why can't we do this for propositional formulas?
* Analog of recursively enumerable becomes NP.
* The reductions he used were Turing reductions not Karp's.

**Tags:** cc.complexity-theory, np-complete, cook-levin

> **Comments:**
> **username_1**: The closes result I know is that the satisfiability problem of first-order logic over finite structures is $\Sigma_1^0$-complete, i.e., complete for the class of computably enumerable languages.  
> **username_2**: Not judging the validity of the original claim, but a  "well-known theorem" which even the speaker "didn't seem to know exactly" seems to be stretching the definition of "well-known" a little.  
> **username_0**: @ReijoJaakkola that helps. It sounds likely that was the result I will confirm. What is a standard reference for that kind of result?  
> **username_3**: I googled **history of NP completeness** and found [this publication by David Johnson](https://www.math.uni-bielefeld.de/documenta/vol-ismp/50_johnson-david.pdf).  
> **username_0**: https://www.youtube.com/watch?v=M_S_pbaMy0o 1:09  
> **username_0**: The notion is defined in his lecture notes http://www.cs.toronto.edu/~sacook/csc438h/  

---

## 1 answers

### Answer by username_4 on 2021-10-10. Score: 1 | Accepted answer

There are *two* results this could plausibly be which nicely contrast each other - they differ on whether we look at finite or infinite structures:

* **([Turing](https://en.wikipedia.org/wiki/Entscheidungsproblem), following [Godel](https://en.wikipedia.org/wiki/G%C3%B6del%27s_completeness_theorem))** The ***validity* problem for first-order logic on *arbitrary* structures** in a sufficiently rich language is $\Sigma^0\_1$-complete; for example, the set of (codes of) sentences true in every directed graph is $\Sigma^0\_1$-complete.
* **([Trakhtenbrot](https://en.wikipedia.org/wiki/Trakhtenbrot%27s_theorem))** The ***satisfiability* problem for first-order logic on *finite* structures** in a sufficiently rich language is $\Sigma^0\_1$-complete; for example, the set of (codes of) sentences true in some finite directed graph is $\Sigma^0\_1$-complete.

> **Comments:**
> **username_4**: Since this is often overlooked, let me observe that by far the most surprising part of either of these results is the upper bound on the validity problem for arbitrary structures, which at first glance is merely $\Pi_1$ in the [Levy hierarchy](https://en.wikipedia.org/wiki/L%C3%A9vy_hierarchy); see the discussion [here](https://math.stackexchange.com/questions/2099531/how-to-verify-satisfialibility-in-a-model-confusions-with-g%C3%B6dels-completeness).  

---

