The P=NP Question and Gödel’s Lost Letter
Lipton, Richard J.
The P=NP Question and Gödel’s Lost Letter [recurso electrónico] / by Richard J. Lipton. - XIII, 239 p. online resource.
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.
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 historical developments (including the Gödel’s Lost letter), the importance of P=NP and the future of P=NP. This guide is also based on a new blog by the author, located at http://rjlipton.wordpress.com. Jin-Yi Cai, a professor in computer science at the University of Wisconsin remarks 'I think it is the single most interesting web blog I have seen on related topics. He has a great insight and wit and beautiful way to see things and explain them.' Richard DeMillo, a professor in computer science at Georgia Tech remarks, 'This is a much needed treatment of great open problem computing.' The P=NP Question and Gödel’s Lost Letter is designed for advanced level students and researchers in computer science, and mathematics as a secondary text and reference book. Computer programmers, software developers and IT professionals working in the related industry of computer science theory, will also find this guide a valuable asset.
9781441971555
Computer science.
Information theory.
Computer software.
Algorithms.
Logic, Symbolic and mathematical.
Computer Science.
Theory of Computation.
Mathematics of Computing.
History of Computing.
Mathematical Logic and Foundations.
Algorithm Analysis and Problem Complexity.
Algorithms.
QA75.5-76.95
004.0151
The P=NP Question and Gödel’s Lost Letter [recurso electrónico] / by Richard J. Lipton. - XIII, 239 p. online resource.
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.
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 historical developments (including the Gödel’s Lost letter), the importance of P=NP and the future of P=NP. This guide is also based on a new blog by the author, located at http://rjlipton.wordpress.com. Jin-Yi Cai, a professor in computer science at the University of Wisconsin remarks 'I think it is the single most interesting web blog I have seen on related topics. He has a great insight and wit and beautiful way to see things and explain them.' Richard DeMillo, a professor in computer science at Georgia Tech remarks, 'This is a much needed treatment of great open problem computing.' The P=NP Question and Gödel’s Lost Letter is designed for advanced level students and researchers in computer science, and mathematics as a secondary text and reference book. Computer programmers, software developers and IT professionals working in the related industry of computer science theory, will also find this guide a valuable asset.
9781441971555
Computer science.
Information theory.
Computer software.
Algorithms.
Logic, Symbolic and mathematical.
Computer Science.
Theory of Computation.
Mathematics of Computing.
History of Computing.
Mathematical Logic and Foundations.
Algorithm Analysis and Problem Complexity.
Algorithms.
QA75.5-76.95
004.0151
