The P=NP Question and Gödel’s Lost Letter
The P=NP question is one of the great 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. The P=NP Question and Gödel’s Lost Letter covers histo...
| Κύριος συγγραφέας: | |
|---|---|
| Συγγραφή απο Οργανισμό/Αρχή: | |
| Μορφή: | Ηλεκτρονική πηγή Ηλ. βιβλίο |
| Γλώσσα: | English |
| Έκδοση: |
Boston, MA :
Springer US,
2010.
|
| Θέματα: | |
| Διαθέσιμο Online: | Full Text via HEAL-Link |
Πίνακας περιεχομένων:
- A Prologue
- A Walk In the Snow
- On the P=NP Question
- Algorithms: Tiny Yet Powerful
- Is P=NP Well 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?
- On Integer Factoring
- Factoring and Factorials
- BDD’s
- Factoring and Fermat
- On Mathematics
- A Curious Algorithm
- Edit Distance
- Protocols
- Erd?s and the Quantum Method
- Amplifiers
- Amplifying on the PCR Amplifier
- Mathematical Embarrassments
- Mathematical Diseases
- Mathematical Surprises
- Erratum.
