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

? DoesP=NP. In just ?ve symbols Dick Karp –in 1972–captured one of the deepest and most important questions of all time. When he ?rst wrote his famous paper, I think it’s fair to say he did not know the depth and importance of his question. Now over three decades later, we know P=NP is central to our understanding of compu- tion, it is a very hard problem, and its resolution will have potentially tremendous consequences. This book is a collection of some of the most popular posts from my blog— Godel ¨ Lost Letter andP=NP—which I started in early 2009. The main thrust of the blog, especially when I started, was to explore various aspects of computational complexity around the famousP=NP question. As I published posts I branched out and covered additional material, sometimes a timely event, sometimes a fun idea, sometimes a new result, and sometimes an old result. I have always tried to make the posts readable by a wide audience, and I believe I have succeeded in doing this.

? DoesP=NP. In just ?ve symbols Dick Karp –in 1972–captured one of the deepest and most important questions of all time. When he ?rst wrote his famous paper, I think it’s fair to say he did not know the depth and importance of his question. Now over three decades later, we know P=NP is central to our understanding of compu- tion, it is a very hard problem, and its resolution will have potentially tremendous consequences. This book is a collection of some of the most popular posts from my blog— Godel ¨ Lost Letter andP=NP—which I started in early 2009. The main thrust of the blog, especially when I started, was to explore various aspects of computational complexity around the famousP=NP question. As I published posts I branched out and covered additional material, sometimes a timely event, sometimes a fun idea, sometimes a new result, and sometimes an old result. I have always tried to make the posts readable by a wide audience, and I believe I have succeeded in doing this.

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.