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