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

By Richard J. Lipton

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

The P=NP question is one of the great problems of science, which has intrigued computer scientists and mathematicians for decades. This guide, originating from a weblog written by the author, covers historical developments and latest approaches to the problem.

Full Description

  • ISBN13: 978-1-4419-7154-8
  • 256 Pages
  • User Level: Science
  • Publication Date: August 20, 2010
  • Available eBook Formats: PDF
  • eBook Price: $99.00
Buy eBook Buy Print Book Add to Wishlist
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. Jin-Yi 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

  1. Part I A Prologue.
  2. A Walk In the Snow.
  3. Part II On the P=NP Question.
  4. Algorithms: Tiny Yet Powerful.
  5. Is P=NP Well Posed?.
  6. What Would You Bet?.
  7. What Happens What P=NP Is Resolved?.
  8. NP Too Big or P Too Small?.
  9. How To Solve P=NP?.
  10. Why Believe P Not Equal To NP?.
  11. A Nightmare About SAT.
  12. Bait and Switch.
  13. Who’s Afraid of Natural Proofs?.
  14. An Approach To P=NP.
  15. Is SAT Easy?.
  16. SAT is Not Too Easy.
  17. Ramsey’s Theorem and NP.
  18. Can They Do That?.
  19. Rabin Flips a Coin.
  20. A Proof We All Missed.
  21. Barrington Gets Simple.
  22. Exponential Algorithms.
  23. An EXPSPACE Lower Bound.
  24. Randomness has Unbounded Power.
  25. Counting Cycles and Logspace.
  26. Ron Graham Gives a Talk.
  27. An Approximate Counting Method.
  28. Easy and Hard Sums.
  29. How To Avoid O
  30. Abuse.
  31. How Good is The Worst Case Model?.
  32. Savitch’s Theorem.
  33. Adaptive Sampling and Timed Adversaries.
  34. On The Intersection of Finite Automata.
  35. Where are the Movies?.
  36. Part III On Integer Factoring.
  37. Factoring and Factorials.
  38. BDD’s.
  39. Factoring and Fermat.
  40. Part IV On Mathematics.
  41. A Curious Algorithm.
  42. Edit Distance.
  43. Protocols.
  44. Erdõs and the Quantum Method.
  45. Amplifiers.
  46. Amplifying on the PCR Amplifier.
  47. Mathematical Embarrassments.
  48. Mathematical Diseases.
  49. Mathematical Surprises.
  50. A Gödel Lost Letter.
  51. Index.
Errata

Please Login to submit errata.

No errata are currently published