Get 1 Year of unlimited Apress for $199  
Instant access to all available titles and new releases 
 Full Description

The P=NP question is one of the great problems of science, which has intrigued computer scientists and mathematicians for decades. Despite the abundant research in theoretical computer science regarding the P=NP question, it has not been solved. The P=NP Question and Gödel’s Lost Letter covers historical developments (including the Gödel’s Lost letter), the importance of P=NP and the future of P=NP. This guide is also based on a new blog by the author, located at http://rjlipton.wordpress.com. JinYi Cai, a Professor in computer science at the University of Wisconsin remarks 'I think it is the single most interesting web blog I have seen on related topics. He has a great insight and wit and beautiful way to see things and explain them.' Richard DeMillo, a professor in computer science at Georgia Tech remarks, 'This is a much needed treatment of great open problem computing.'The P=NP Question and Gödel’s Lost Letter is designed for advanced level students and researchers in computer science, and mathematics as a secondary text and reference book. Computer programmers, software developers and IT professionals working in the related industry of computer science theory, will also find this guide a valuable asset.
 Table of Contents

Table of Contents
 Part I A Prologue.
 A Walk In the Snow.
 Part II On the P=NP Question.
 Algorithms: Tiny Yet Powerful.
 Is P=NP Well Posed?.
 What Would You Bet?.
 What Happens What 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?.
 Part III On Integer Factoring.
 Factoring and Factorials.
 BDD’s.
 Factoring and Fermat.
 Part IV 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.
 A Gödel Lost Letter.
 Index.
 Errata

If you think that you've found an error in this book, please let us know by emailing to editorial@apress.com . You will find any confirmed erratum below, so you can check if your concern has already been addressed.
No errata are currently published