The P=NP question and Gödel's lost letter
By: Richard J. Lipton
Contributors: Gödel, Kurt
Publisher: Springer
Published: 2010
Place of publication: New York
Language: eng
Format: Hardcover
Number of pages: 239
ISBN-13: 9781441971548; 9781441971555
Subjects: Computer algorithms; Computational complexity; Symbolic and mathematical Logic; Gödel's theorem
Other titles: P equals NP question and Gödel's lost letter
Description: The P=NP question is one of the greatest 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. This book 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 -- Back cover.
Notes: Includes bibliographical references (p. 229-233) and index.
Table of contents: title: Preface
pagenum: vii; title: Acknowledgments
pagenum: ix; title: Contents
pagenum: xi; label: Part I
title: A Prologue; label: 1
title: A Walk In the Snow
pagenum: 3; label: Part II
title: On the P=NP Question; label: 2
title: Algorithms: Tiny Yet Powerful
pagenum: 9; label: 3
title: Is P=NP Well Posed?
pagenum: 13; label: 4
title: What Would You Bet?
pagenum: 19; label: 5
title: What Happens When P=NP Is Resolved?
pagenum: 23; label: 6
title: NP Too Big or P Too Small?
pagenum: 27; label: 7
title: How To Solve P=NP?
pagenum: 29; label: 8
title: Why Believe P Not Equal To NP?
pagenum: 33; label: 9
title: A Nightmare About SAT
pagenum: 37; label: 10
title: Bait and Switch
pagenum: 39; label: 11
title: Who's Afraid of Natural Proofs?
pagenum: 43; label: 12
title: An Approach To P=NP
pagenum: 49; label: 13
title: Is SAT Easy?
pagenum: 55; label: 14
title: SAT is Not Too Easy
pagenum: 61; label: 15
title: Ramsey's Theorem and NP
pagenum: 67; label: 16
title: Can They Do That?
pagenum: 71; label: 17
title: Rabin Flips a Coin
pagenum: 77; label: 18
title: A Proof We All Missed
pagenum: 81; label: 19
title: Barrington Gets Simple
pagenum: 85; label: 20
title: Exponential Algorithms
pagenum: 89; label: 21
title: An EXPSPACE Lower Bound
pagenum: 93; label: 22
title: Randomness has Unbounded Power
pagenum: 99; label: 23
title: Counting Cycles and Logspace
pagenum: 105; label: 24
title: Ron Graham Gives a Talk
pagenum: 111; label: 25
title: An Approximate Counting Method
pagenum: 115; label: 26
title: Easy and Hard Sums
pagenum: 119; label: 27
title: How To Avoid O-Abuse
pagenum: 127; label: 28
title: How Good is The Worst Case Model?
pagenum: 129; label: 29
title: Savitch's Theorem
pagenum: 135; label: 30
title: Adaptive Sampling and Timed Adversaries
pagenum: 139; label: 31
title: On The Intersection of Finite Automata
pagenum: 145; label: 32
title: Where are the Movies?
pagenum: 149; label: Part III
title: On Integer Factoring; label: 33
title: Factoring and Factorials
pagenum: 153; label: 34
title: BDDs
pagenum: 157; label: 35
title: Factoring and Fermat
pagenum: 165; label: Part IV
title: On Mathematics; label: 36
title: A Curious Algorithm
pagenum: 173; label: 37
title: Edit Distance
pagenum: 179; label: 38
title: Protocols
pagenum: 185; label: 39
title: Erdos and the Quantum Method
pagenum: 189; label: 40
title: Amplifiers
pagenum: 195; label: 41
title: Amplifying on the PCR Amplifier
pagenum: 201; label: 42
title: Mathematical Embarrassments
pagenum: 209; label: 43
title: Mathematical Diseases
pagenum: 215; label: 44
title: Mathematical Surprises
pagenum: 219; label: A
title: A Godel Lost Letter
pagenum: 227; title: References
pagenum: 229; title: Index
pagenum: 235