Suchen und Finden
The P=NP Question and Gödel's Lost Letter
von: Richard J. Lipton
Springer-Verlag, 2010
ISBN: 9781441971555 , 239 Seiten
Format: PDF, OL
Kopierschutz: Wasserzeichen
Preis: 96,29 EUR
Preface
6
Acknowledgements
8
Contents
9
A Prologue
12
A Walk In the Snow
13
On the P=NP Question
16
Algorithms: Tiny Yet Powerful
17
Is P=NPWell Posed?
20
What Would You Bet?
25
What Happens When P= NP Is Resolved?
28
NP Too Big or P Too Small?
32
How To Solve P=NP?
34
Why Believe P Not Equal To NP?
37
A Nightmare About SAT
41
Bait and Switch
43
Who’s Afraid of Natural Proofs?
46
An Approach To P= NP
52
Is SAT Easy?
57
SAT is Not Too Easy
63
Ramsey’s Theorem and NP
68
Can They Do That?
72
Rabin Flips a Coin
77
A ProofWe All Missed
81
Barrington Gets Simple
84
Exponential Algorithms
88
An EXPSPACE Lower Bound
91
Randomness has Unbounded Power
97
Counting Cycles and Logspace
102
Ron Graham Gives a Talk
107
An Approximate Counting Method
111
Easy and Hard Sums
115
How To Avoid O-Abuse
122
How Good is The Worst Case Model?
124
Savitch’s Theorem
129
Adaptive Sampling and Timed Adversaries
133
On The Intersection of Finite Automata
139
Where are the Movies?
143
On Integer Factoring
145
Factoring and Factorials
146
BDD’s
150
Factoring and Fermat
157
On Mathematics
162
A Curious Algorithm
163
Edit Distance
169
Protocols
174
Erdös and the Quantum Method
178
Amplifiers
183
Amplifying on the PCR Amplifier
188
Mathematical Embarrassments
195
Mathematical Diseases
200
Mathematical Surprises
204
Gödel Lost Letter
212
Index
219
Alle Preise verstehen sich inklusive der gesetzlichen MwSt.