25 Years of P versus NP
Lance Fortnow
University of Chicago
25 Years of P versus NP
1971
1971
1971
1971 - And in Shaker Heights...
Boolean Formula Satisfiability
P versus NP
1972 - Combinatorial Problems
3 Coloring
3 Coloring
3 Coloring
3 Coloring
3 Coloring
3 Coloring
3 Coloring
3 Coloring
3 Coloring
3 Coloring
3 Coloring
Does P = NP?
A Tour of P versus NP
Separation
Circuits
Circuits from 1981 to 1987
Probabilistic Computation
Approximation Algorithms
Hard to Three Color
Easy to Four Color
Approximation Algorithms
Not 3 Colorable
Not 3 Colorable
Not 3 Colorable
I Lied
Not 3 Colorable
Interactive Proof Systems
Cryptography
Zero-Knowledge
Zero-Knowledge
Zero-Knowledge
Zero-Knowledge
Zero-Knowledge
Zero-Knowledge
Zero-Knowledge
Zero-Knowledge
Zero-Knowledge
Biological Computing
Quantum Computing
Future Challenges