The P=NP question and Gödel's lost letter

  • 1 Want to read

My Reading Lists:

Create a new list


  • 1 Want to read


Download Options

Buy this book

Last edited by MARC Bot
July 6, 2019 | History

The P=NP question and Gödel's lost letter

  • 1 Want to read

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.

Publish Date
Publisher
Springer
Language
English
Pages
239

Buy this book

Previews available in: English

Edition Availability
Cover of: The P=NP question and Gödel's lost letter
The P=NP question and Gödel's lost letter
2010, Springer
Hardcover in English

Add another edition?

Book Details


Table of Contents

Preface
Page vii
Acknowledgments
Page ix
Contents
Page xi
Part I. A Prologue
1. A Walk In the Snow
Page 3
Part II. On the P=NP Question
2. Algorithms: Tiny Yet Powerful
Page 9
3. Is P=NP Well Posed?
Page 13
4. What Would You Bet?
Page 19
5. What Happens When P=NP Is Resolved?
Page 23
6. NP Too Big or P Too Small?
Page 27
7. How To Solve P=NP?
Page 29
8. Why Believe P Not Equal To NP?
Page 33
9. A Nightmare About SAT
Page 37
10. Bait and Switch
Page 39
11. Who's Afraid of Natural Proofs?
Page 43
12. An Approach To P=NP
Page 49
13. Is SAT Easy?
Page 55
14. SAT is Not Too Easy
Page 61
15. Ramsey's Theorem and NP
Page 67
16. Can They Do That?
Page 71
17. Rabin Flips a Coin
Page 77
18. A Proof We All Missed
Page 81
19. Barrington Gets Simple
Page 85
20. Exponential Algorithms
Page 89
21. An EXPSPACE Lower Bound
Page 93
22. Randomness has Unbounded Power
Page 99
23. Counting Cycles and Logspace
Page 105
24. Ron Graham Gives a Talk
Page 111
25. An Approximate Counting Method
Page 115
26. Easy and Hard Sums
Page 119
27. How To Avoid O-Abuse
Page 127
28. How Good is The Worst Case Model?
Page 129
29. Savitch's Theorem
Page 135
30. Adaptive Sampling and Timed Adversaries
Page 139
31. On The Intersection of Finite Automata
Page 145
32. Where are the Movies?
Page 149
Part III. On Integer Factoring
33. Factoring and Factorials
Page 153
34. BDDs
Page 157
35. Factoring and Fermat
Page 165
Part IV. On Mathematics
36. A Curious Algorithm
Page 173
37. Edit Distance
Page 179
38. Protocols
Page 185
39. Erdos and the Quantum Method
Page 189
40. Amplifiers
Page 195
41. Amplifying on the PCR Amplifier
Page 201
42. Mathematical Embarrassments
Page 209
43. Mathematical Diseases
Page 215
44. Mathematical Surprises
Page 219
A. A Godel Lost Letter
Page 227
References
Page 229
Index
Page 235

Edition Notes

Includes bibliographical references (p. 229-233) and index.

Published in
New York
Other Titles
P equals NP question and Gödel's lost letter

Classifications

Dewey Decimal Class
511.3
Library of Congress
QA9.65 .L57 2010, QA75.5-76.95

The Physical Object

Format
Hardcover
Pagination
xiii, 239 p.
Number of pages
239
Weight
530 grams

Edition Identifiers

Open Library
OL25249754M
Internet Archive
pnpquestiongodel00lipt
ISBN 10
1441971548
ISBN 13
9781441971548, 9781441971555
LCCN
2010932770
OCLC/WorldCat
671868992

Work Identifiers

Work ID
OL16561313W

Work Description

A collection of blog postings about topics in complexity theory and other related mathematics.

Community Reviews (0)

No community reviews have been submitted for this work.

Lists

History

Download catalog record: RDF / JSON
July 6, 2019 Edited by MARC Bot import existing book
April 20, 2012 Edited by 108.35.58.254 added a description
March 21, 2012 Created by LC Bot import new book