E-book

The P=NP Question and Gödel’s Lost Letter [electronic resource] / by Richard J. Lipton.

Record details

Subject:

Add to basket View My Basket Print Email Permalink Disable Highlighting

Table of Contents

	Preface	vii
	Acknowledgments	ix
	Contents	xi
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.	BDDs	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.	A Godel Lost Letter	227
	References	229
	Index	235