The P=NP Question and Gödel’s Lost Letter

Richard Lipton is the Storey Professor of Computer Science at Georgia Institute of Technology. Previously he held faculty positions at Yale University, the University of California at Berkeley, and Princeton University. His research is focused primarily, but not exclusively, on theory of computation. He has made seminal contributions to many areas of computing from software engineering and program testing, to computer security and cryptography, to DNA and molecular computation, and to other areas of computer science. He is a member of The National Academy of Engineering, an ACM Fellow, and a Guggenheim fellow.

A Prologue.- A Walk In the Snow.- On the P=NP Question.- Algorithms: Tiny Yet Powerful.- Is P=NP Well Posed?.- What Would You Bet?.- What Happens When P=NP Is Resolved?.- NP Too Big or P Too Small?.- How To Solve P=NP?.- Why Believe P Not Equal To NP?.- A Nightmare About SAT.- Bait and Switch.- Who’s Afraid of Natural Proofs?.- An Approach To P=NP.- Is SAT Easy?.- SAT is Not Too Easy.- Ramsey’s Theorem and NP.- Can They Do That?.- Rabin Flips a Coin.- A Proof We All Missed.- Barrington Gets Simple.- Exponential Algorithms.- An EXPSPACE Lower Bound.- Randomness has Unbounded Power.- Counting Cycles and Logspace.- Ron Graham Gives a Talk.- An Approximate Counting Method.- Easy and Hard Sums.- How To Avoid O-Abuse.- How Good is The Worst Case Model?.- Savitch’s Theorem.- Adaptive Sampling and Timed Adversaries.- On The Intersection of Finite Automata.- Where are the Movies?.- On Integer Factoring.- Factoring and Factorials.- BDD’s.- Factoring and Fermat.- On Mathematics.- A Curious Algorithm.- Edit Distance.- Protocols.- Erd?s and the Quantum Method.- Amplifiers.- Amplifying on the PCR Amplifier.- Mathematical Embarrassments.- Mathematical Diseases.- Mathematical Surprises.- Erratum.