02621nam a2200301Ia 4500001001500000003000800015005001700023006001900040007000700059008004100066020003200107040002100139100003800160245015100198260003600349300002400385500002900409504006400438505034700502520112400849530003701973538003602010650003002046655002802076700003002104776002902134856015602163CAH0KE14034PDFFlBoTFG20171224123542.0m|||||o||d||||||||cr||||121226s2013    fluad   sb    001 0 eng d  a9781439882078 (ebook : PDF)  aFlBoTFGcFlBoTFG1 aReiter, Edna E.q(Edna Elizabeth)10aLimits of computationh[electronic resource] :ban introduction to the undecidable and the intractable /cEdna E. Reiter, Clayton Matthew Johnson.  aBoca Raton :bCRC Press,c2013.  axix, 259 p. :bill.  a"A Chapman & Hall book."  aIncludes bibliographical references (p. 253-254) and index.0 ach. 1. Set theory -- ch. 2. Languages : alphabets, strings, and languages -- ch. 3. Algorithms -- ch. 4. Turing machines -- ch. 5. Turing-completeness -- ch. 6. Undecidability -- ch. 7. Undecidability and reducibility -- ch. 8. Classes NP and NP-complete -- ch. 9. More NP-complete problems -- ch. 10. Other interesting questions and classes.  a"Preface To the student: We think that the theory dealing with what is hard about computation (and what is impossible!) is challenging but fun. This book grows out of these ideas, and our approach to teaching a course in computational complexity. There is no doubt that some of the material in these chapters is what might be called "wrap your brain around it" material, where a first reaction might be that the authors are pulling off a trick like a magician pulling a rabbit out of a hat. For instance, consider the proof--using proof by contradiction--that there can be no algorithm to tell whether a program written in C++ will go into an infinite loop. One reaction upon reaching the contradiction at the end of the proof might be that there must be a misstep somewhere in the proof; another might be that there cannot really be a contradiction. Only after reading, rereading, and carefully considering each step can the student buy in to the proof. There are no shortcuts here; this is not reading to be done with the television playing in the background. There are also diversions here, such as the bridges of K.  aAlso available in print edition.  aMode of access: World Wide Web. 0aComputational complexity. 7aElectronic books.2lcsh1 aJohnson, Clayton Matthew.1 z9781439882061 (hardback)40uhttp://marc.crcnetbase.com/isbn/9781439882078qapplication/PDFzDistributed by publisher. Purchase or institutional license may be required for access.