The P=NP Question and Gödel’s Lost Letter [recurso electrónico] / by Richard J. Lipton.

Por: Lipton, Richard J [author.]Colaborador(es): SpringerLink (Online service)Tipo de material: TextoTextoEditor: Boston, MA : Springer US, 2010Descripción: XIII, 239 p. online resourceTipo de contenido: text Tipo de medio: computer Tipo de portador: online resourceISBN: 9781441971555Tema(s): 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 | AlgorithmsFormatos físicos adicionales: Printed edition:: Sin títuloClasificación CDD: 004.0151 Clasificación LoC:QA75.5-76.95Recursos en línea: Libro electrónicoTexto
Contenidos:
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.
En: Springer eBooksResumen: 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.
Star ratings
    Valoración media: 0.0 (0 votos)
Existencias
Tipo de ítem Biblioteca actual Colección Signatura Copia número Estado Fecha de vencimiento Código de barras
Libro Electrónico Biblioteca Electrónica
Colección de Libros Electrónicos QA75.5 -76.95 (Browse shelf(Abre debajo)) 1 No para préstamo 371839-2001

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.

19

Con tecnología Koha