The P=NP Question and Gödel's Lost Letter (PDF)

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.

“This book is a thoroughly enjoyable read because ofthe great balance between anecdotes, presentations of ‘nice’ problems andalgorithms and their solutions and proofs, ‘hard mathematics,’ and musings onhow to approach mathematical problems. After having read the book, most readerswith a background in complexity theory will most likely be unable to resistimmediately working on at least one of the many open problems presented in thebook.” (Till Tantau, Mathematical Reviews, October, 2015)

“This book … collects and edits the highlights from Lipton’s ongoing blog, rounded out by cross-references and a useful index and bibliography. … the book offers a different experience and a framed portrait of the state of the art. … Summing Up: Recommended. All levels/libraries.” (D. V. Feldman, Choice, Vol. 48 (9), May, 2011)

“The P=NP question is certainly one of the most important problems in mathematics and computer science (CS). What makes this book unique and delightful is that it gives proper weight to the question rather than the technicalities. Each chapter is based on one of Lipton’s blog posts, and readers can jump from chapter to chapter to find his beautifully written thoughts and insights. … In fact, anyone who is highly motivated by this interesting subject that relates science with reality should read it.” (Hector Zenil, ACM Computing Reviews, March, 2011)

“This book collects some entries of the author’s blog on Gödel’s lost letter and P = NP … . It is an enjoyable and lively introduction to some impressive achievements in the field of complexity theory.” (Thierry Coquand, Zentralblatt MATH, Vol. 1215, 2011)