P=Np Question and G�del's Lost Letter

ISBN-10: 1441971548
ISBN-13: 9781441971548
Authors: Richard J. Lipton
List price: $119.00

FREE return shipping at the end of the semester -

Out of stock


Author bio:

Richard Lipton is the Storey Professor of Computer Science at Georgia Institute of Technology. Previously he held faculty positions at Yale University, the University of California at Berkeley, and Princeton University. His research is focused primarily, but not exclusively, on theory of computation. He has made seminal contributions to many areas of computing from software engineering and program testing, to computer security and cryptography, to DNA and molecular computation, and to other areas of computer science. He is a member of The National Academy of Engineering, an ACM Fellow, and a Guggenheim fellow.


Customers also bought

Product details

Binding: Hardcover Publisher: Springer Number of pages: 239 Dimensions: 6.50" wide x 9.50" long x 0.75" tall Weight: 1.144 lbs. Language: English

Table of contents

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
Factoring and Fermat
On Mathematics
A Curious Algorithm
Edit Distance
Erdos and the Quantum Method
Amplifying on the PCR Amplifier
Mathematical Embarrassments
Mathematical Diseases
Mathematical Surprises
G�del Lost Letter