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 athttp://rjlipton.wordpress.com. Jin-Yi Cai, an Associate Professor in computerscience at the University of Wisconsin remarks 'I think it is the single mostinteresting 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. A cutting edge discussion of the 'The P=NP Question' Includes free access to the author’s blog 'The P=NP Question' 'This is a much needed treatment of great open problem computing,' states Richard Demillo, Professor, Georgia Institute of Technology INDICE: 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’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.- CountingCycles 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.- Erdõs and the Quantum Method.- Amplifiers.- Amplifying on the PCR Amplifier.- Mathematical Embarrassments.- Mathematical Diseases.- Mathematical Surprises.- A Gödel Lost Letter.- Index.
- ISBN: 978-1-4419-7154-8
- Editorial: Springer
- Encuadernacion: Cartoné
- Páginas: 244
- Fecha Publicación: 29/08/2010
- Nº Volúmenes: 1
- Idioma: Inglés