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)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson? Leonid Levin

Emacs 29.4 (Org mode 9.6.15)