000 04179nam a22005295i 4500
001 978-1-4419-7155-5
003 DE-He213
005 20140220084511.0
007 cr nn 008mamaa
008 100825s2010 xxu| s |||| 0|eng d
020 _a9781441971555
_9978-1-4419-7155-5
024 7 _a10.1007/978-1-4419-7155-5
_2doi
050 4 _aQA75.5-76.95
072 7 _aUY
_2bicssc
072 7 _aUYA
_2bicssc
072 7 _aCOM014000
_2bisacsh
072 7 _aCOM031000
_2bisacsh
082 0 4 _a004.0151
_223
100 1 _aLipton, Richard J.
_eauthor.
245 1 4 _aThe P=NP Question and Gödel’s Lost Letter
_h[electronic resource] /
_cby Richard J. Lipton.
264 1 _aBoston, MA :
_bSpringer US,
_c2010.
300 _aXIII, 239p. 20 illus.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
505 0 _aA 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.
520 _aThe 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.
650 0 _aComputer science.
650 0 _aInformation theory.
650 0 _aComputer software.
650 0 _aAlgorithms.
650 0 _aLogic, Symbolic and mathematical.
650 1 4 _aComputer Science.
650 2 4 _aTheory of Computation.
650 2 4 _aMathematics of Computing.
650 2 4 _aHistory of Computing.
650 2 4 _aMathematical Logic and Foundations.
650 2 4 _aAlgorithm Analysis and Problem Complexity.
650 2 4 _aAlgorithms.
710 2 _aSpringerLink (Online service)
773 0 _tSpringer eBooks
776 0 8 _iPrinted edition:
_z9781441971548
856 4 0 _uhttp://dx.doi.org/10.1007/978-1-4419-7155-5
912 _aZDB-2-SCS
999 _c110725
_d110725