Издательство Springer, 2010, -222 pp.
Does P=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 computation, 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— G?del Lost Letter and P=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 famous P=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.
One of the things I think people sometimes forget is that research is done by people. I wanted to make the posts people oriented. I have over the years tried to talk about the who as much as the what. One of my goals—perhaps the main one—is to get you to be able to see behind the curtain and understand how research works. It is a secret agenda of mine to explain what real researchers do when they work on open problems. They make mistakes, they go down dead-ends, they make progress. Students may not know, but even experts sometimes forget, that ideas that we now see as easy were once unknown. This agenda is the main reason that I have made the blog people oriented. Since I have over 30 years of experience working in theory, I know almost everyone that I write about. I think this makes the discussions more interesting, and I hope that you will agree.
I am Dick Lipton, a Professor of Computer Science at Georgia Tech. I have worked in the area of theory of computation since 1973. I find the whole area exciting and want to share some of that excitement with you—I hope that these chapters inform and entertain you. I hope that you not only lea some new ideas, hear some interesting open problems, but also get some of the history of the area. One of the things I think people sometimes forget is that research is done by people. One of my goals—perhaps the main one—is to get you to be able to see behind the curtain and understand how research works.
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 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 ProofWe 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?
Part III On Integer Factoring
Factoring and Factorials
BDD’s
Factoring and Fermat
Part IV On Mathematics
A Curious Algorithm
Edit Distance
Protocols
Erdos and the Quantum Method
Amplifiers
Amplifying on the PCR Amplifier
Mathematical Embarrassments
Mathematical Diseases
Mathematical Surprises
A G?del Lost Letter
Does P=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 computation, 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— G?del Lost Letter and P=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 famous P=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.
One of the things I think people sometimes forget is that research is done by people. I wanted to make the posts people oriented. I have over the years tried to talk about the who as much as the what. One of my goals—perhaps the main one—is to get you to be able to see behind the curtain and understand how research works. It is a secret agenda of mine to explain what real researchers do when they work on open problems. They make mistakes, they go down dead-ends, they make progress. Students may not know, but even experts sometimes forget, that ideas that we now see as easy were once unknown. This agenda is the main reason that I have made the blog people oriented. Since I have over 30 years of experience working in theory, I know almost everyone that I write about. I think this makes the discussions more interesting, and I hope that you will agree.
I am Dick Lipton, a Professor of Computer Science at Georgia Tech. I have worked in the area of theory of computation since 1973. I find the whole area exciting and want to share some of that excitement with you—I hope that these chapters inform and entertain you. I hope that you not only lea some new ideas, hear some interesting open problems, but also get some of the history of the area. One of the things I think people sometimes forget is that research is done by people. One of my goals—perhaps the main one—is to get you to be able to see behind the curtain and understand how research works.
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 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 ProofWe 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?
Part III On Integer Factoring
Factoring and Factorials
BDD’s
Factoring and Fermat
Part IV On Mathematics
A Curious Algorithm
Edit Distance
Protocols
Erdos and the Quantum Method
Amplifiers
Amplifying on the PCR Amplifier
Mathematical Embarrassments
Mathematical Diseases
Mathematical Surprises
A G?del Lost Letter