STOC 2021 - 50th Anniversary of the Cook-Levin Theorem - 2021
Details
Title : STOC 2021 - 50th Anniversary of the Cook-Levin Theorem Author(s): SIGACT EC Link(s) : https://www.youtube.com/watch?v=UgGGXXkYqsM
Rough Notes
NP-Completeness: A Personal Perspective, Stephen Cook
"In what way is multiplication harder than addition?"
This question by Alan Cobham that influenced Stephen Cook.
STOC 1971 : The Complexity of Theorem-Proving Procedures
- Problems solved by a poly-time nondeterministic Turing machine can be reduced to \(\{\text{tautologies}\}\).
The set \(\{\text{tautologies}\}\) is a difficult set to recognize. Many "hard" problems can be reduced to the problem of determining whether a given formula is a tautology. Hence, if an oracle is available to recognize \(\{\text{tautologies}\}\), the "hard" problems can be solved deterministically in polynomial time.
Query machine (Kreider and Ritchie 1964)