The P=NP Question and G�del's Lost Letter

by Richard J. Lipton

Overview

? DoesP=NP. In just five symbols Dick Karp –in 1972–captured one of the deepest and most important questions of all time. When he first wrote his famous paper, I think it’s fair to say he did not know the depth and importance of his question. Now over three decades later, we know P=NP is central to our understanding of compu- tion, it is a very hard problem, and its resolution will have potentially tremendous consequences. This book is a collection of some of the most popular posts from my blog— Godel ¨ Lost Letter andP=NP—which I started in early 2009. The main thrust of the blog, especially when I started, was to explore various aspects of computational complexity around the famousP=NP question. As I published posts I branched out and covered additional material, sometimes a timely event, sometimes a fun idea, sometimes a new result, and sometimes an old result. I have always tried to make the posts readable by a wide audience, and I believe I have succeeded in doing this.

Product Details

ISBN-13:	9781441971548
Publisher:	Springer US
Publication date:	09/01/2010
Edition description:	2010
Pages:	239
Product dimensions:	6.10(w) x 9.25(h) x 0.24(d)

About the Author

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.

Table of Contents

Part I A Prologue

1 A Walk In the Snow 3

Part II On the P=NP Question

2 Algorithms: Tiny Yet Powerful 9

3 Is P=NP Well Posed? 13

4 What Would You Bet? 19

5 What Happens When P=NP Is Resolved? 23

6 NP Too Big or P Too Small? 27

7 How To Solve P=NP? 29

8 Why Believe P Not Equal To NP? 33

9 A Nightmare About SAT 37

10 Bait and Switch 39

11 Who's Afraid of Natural Proofs? 43

12 An Approach To P=NP 49

13 Is SAT Easy? 55

14 SAT is Not Too Easy 61

15 Ramsey's Theorem and NP 67

16 Can They Do That? 71

17 Rabin Flips a Coin 77

18 A Proof We All Missed 81

19 Barrington Gets Simple 85

20 Exponential Algorithms 89

21 An EXPSPACE Lower Bound 93

22 Randomness has Unbounded Power 99

23 Counting Cycles and Logspace 105

24 Ron Graham Gives a Talk 111

25 An Approximate Counting Method 115

26 Easy and Hard Sums 119

27 How To Avoid O-Abuse 127

28 How Good is The Worst Case Model? 129

29 Savitch's Theorem 135

30 Adaptive Sampling and Timed Adversaries 139

31 On The Intersection of Finite Automata 145

32 Where are the Movies? 149

Part III On Integer Factoring

33 Factoring and Factorials 153

34 BDD's 157

35 Factoring and Fermat 165

Part IV On Mathematics

36 A Curious Algorithm 173

37 Edit Distance 179

38 Protocols 185

39 Erdos and the Quantum Method 189

40 Amplifiers 195

41 Amplifying on the PCR Amplifier 201

42 Mathematical Embarrassments 209

43 Mathematical Diseases 215

44 Mathematical Surprises 219

A Gödel Lost Letter 227

Index 235

Editorial Reviews

This book is a thoroughly enjoyable read because of the great balance between anecdotes, presentations of ‘nice’ problems and algorithms and their solutions and proofs, ‘hard mathematics,’ and musings on how to approach mathematical problems. After having read the book, most readers with a background in complexity theory will most likely be unable to resist immediately working on at least one of the many open problems presented in the book.” (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)

From the Publisher