# 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)