Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [cook-levin]

The tag has no usage guidance.

9
votes
1answer
1k 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 ...
6
votes
1answer
562 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 ...
8
votes
0answers
334 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{...