The Logic Path
Overview
The Logic Path traces from Huntington's theorem (Boole's Boolean) to SAT · NP-completeness · Complexity theory. Density: extremely high.
Interpretable in: zfc-path
Nodes
- Huntington's theorem (Boole's Boolean)
- Shannon's switching circuits
- Davis–Putnam algorithm
- Cook–Levin theorem
- Levin's theorem (NP-completeness)
- Karp's 21 NP-complete problems
- Time hierarchy theorem
- Savitch's theorem
- Goldreich–Micali–Wigderson zero-knowledge
- Bourgain sum-product and additive combinatorics