Questions tagged [cook-levin]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
108 views

Cook-Levin Theorem implies a transformation from witnesses to witnesses

The book by Wigderson includes this quote on page 39, following the statement of the Cook-Levin theorem that $SAT$ is $\mathsf{NP}$-complete: The proof of this theorem (namely, the construction of ...
abrahimladha's user avatar
8 votes
1 answer
315 views

Cook inspiration for NP completeness

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 ...
user1868607's user avatar
  • 1,017
9 votes
1 answer
2k views

Did Stephen Cook see the significance of showing that SAT is NP-Hard before actually proving it?

If I understand correctly, to prove that problem $A$ is NP hard, you need to pick all possible problems $B_{i}$ that are in NP and then prove that they reduce to $A$ by using a polynomial time ...
jsguy's user avatar
  • 209
6 votes
1 answer
1k views

Does the Cook-Levin theorem relativize?

My only motivation for asking this question is long-standing curiosity, but I am interested in seeing a proof (or disproof) that the Cook-Levin theorem relativizes. If you have a proof that the ...
user avatar
13 votes
0 answers
539 views

Are there any implementations of Cook-Levin?

Does anyone know if there is an implementation of Cook-Levin? A program that gets an input like the following: $M$: the code of a machine model/simple program in a programming language like C, $\vec{...
Kaveh's user avatar
  • 21.6k