The P=NP Question and Gd̲el<U+0019>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 Gd̲el<U+0019>s Lost Letter...
| Main Author: | |
|---|---|
| Corporate Author: | |
| Format: | Electronic |
| Language: | English |
| Published: |
Boston, MA :
Springer US,
2010.
|
| Subjects: | |
| Online Access: | https://ezaccess.library.uitm.edu.my/login?url=http://dx.doi.org/10.1007/978-1-4419-7155-5 |
Table of Contents:
- Part I A Prologue
- A Walk In the Snow
- Part II On the P=NP Question
- Algorithms: Tiny Yet Powerful
- Is P=NP Well Posed?
- What Would You Bet?
- What Happens What 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<U+0019>s Afraid of Natural Proofs?
- An Approach To P=NP
- Is SAT Easy?
- SAT is Not Too Easy
- Ramsey<U+0019>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<U+0019>s Theorem
- Adaptive Sampling and Timed Adversaries
- On The Intersection of Finite Automata
- Where are the Movies?
- Part III On Integer Factoring
- Factoring and Factorials
- BDD<U+0019>s
- Factoring and Fermat
- Part IV On Mathematics
- A Curious Algorithm
- Edit Distance
- Protocols
- Erds̳ and the Quantum Method
- Amplifiers
- Amplifying on the PCR Amplifier
- Mathematical Embarrassments
- Mathematical Diseases
- Mathematical Surprises
- A Gd̲el Lost Letter
- Index.