The P=NP question and Gödel's lost letter / Richard J. Lipton.
| Author/creator | Lipton, Richard J. |
| Other author | Gödel, Kurt. |
| Format | Electronic |
| Publication Info | New York. : Springer, |
| Description | xiii, 239 p. : ill. ; 24 cm. |
| Supplemental Content | Full text available from Springer Books |
| Supplemental Content | Full text available from Springer Nature - Springer Computer Science eBooks 2010 English International |
| Subjects |
| Other title | P equals NP question and Gödel's lost letter |
| Contents | Part I. A prologue. -- A walk in the snow -- Part II. On the P=NP question. -- Algorithms: tiny yet powerful -- Is P=NP 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? -- Part III. On integer factoring. -- Factoring and factorials -- BDD's -- Factoring and Fermat -- Part IV. On mathematics. -- A curious logorithm -- Edit distance -- Protocols -- Erdos and the Quantum Method -- Amplifiers -- Amplifying on the PCR amplifier -- Mathematical embarrassments -- Mathematical diseases -- Mathematical surprises -- Erratum A. Gödel lost letter. |
| Abstract | 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. |
| Bibliography note | Includes bibliographical references (p. 229-233) and index. |
| Access restriction | Available only to authorized users. |
| Technical details | Mode of access: World Wide Web |
| Genre/form | Electronic books. |
| LCCN | 2010932770 |
| ISBN | 9781441971548 |
| ISBN | 1441971548 |
Availability
| Library | Location | Call Number | Status | Item Actions |
|---|---|---|---|---|
| Electronic Resources | ✔ Available |