Limits of computation : an introduction to the undecidable and the intractable
 Responsibility
 Edna E. Reiter, Clayton Matthew Johnson.
 Language
 English.
 Publication
 Boca Raton, FL : CRC Press, Taylor & Francis Group, [2013]
 Copyright notice
 ©2013
 Physical description
 xix, 259 pages ; 24 cm
Access
Creators/Contributors
 Author/Creator
 Reiter, Edna E. (Edna Elizabeth)
 Contributor
 Johnson, Clayton Matthew.
Contents/Summary
 Bibliography
 Includes bibliographical references (pages 253254) and index.
 Contents

 Set Theory SetsBasic Terms Functions Cardinalities Counting Arguments and Diagonalization Languages: Alphabets, Strings, and Languages Alphabets and Strings Operations on Strings Operations on Languages Algorithms Computational Problems Decision Problems Traveling Salesman Problem Algorithms: A First Look History Efficiency in Algorithms Counting Steps in an Algorithm Definitions Useful Theorems Properties of O Notation Finding O: Analyzing an Algorithm Best and Average Case Analysis Tractable and Intractable Turing Machines Overview The Turing Machine Model Formal Definition of Turing Machine Configurations of Turing Machines Terminology Some Sample Turing Machines Turing Machines: What Should I Be Able to Do? TuringCompleteness Other Versions of Turing Machines Turing Machines to Evaluate a Function E numerating Turing Machines The ChurchTuring Thesis A Simple Computer Encodings of Turing Machines Universal Turing Machine Undecidability Introduction and Overview SelfReference and SelfContradiction in Computer Programs Cardinality of the Set of All Languages over an Alphabet Cardinality of the Set of All Turing Machines Construction of the Undecidable Language ACCEPTTM Undecidability and Reducibility Undecidable Problems: Other Examples Reducibility Reducibility and Language Properties Reducibility to Show Undecidability Rice's Theorem (a SuperTheorem) Undecidability: What Does It Mean? Post Correspondence Problem ContextFree Grammars Classes NP and NPComplete The Class NP (Nondeterministic Polynomial) Definition of P and NP Polynomial Reducibility Properties Completeness Intractable and TractableOnce Again A First NPComplete Problem: Boolean Satisfiability CookLevin Theorem: Proof Conclusion More NPComplete Problems Adding Other Problems to the List of Known NPComplete Problems Reductions to Prove NPCompleteness Graph Problems Vertex Cover: The First Graph Problem Other Graph Problems Hamiltonian Circuit (HC) Eulerian Circuits (an Interesting Problem in P) ThreeDimensional Matching (3DM) Subset Sum Summary and Reprise Other Interesting Questions and Classes Introduction Number Problems Complement Classes Open Quest ions Are There Any Problems in NPP But Not NPComplete? PSPACE Reachable Configurations NPSPACE = PSPACE A PSPACE Complete Problem Other PSPACEComplete Problems The Class EXP Space Restrictions Approaches to Hard Problems in Practice Summary Bibliography Index Exercises appear at the end of each chapter.
 (source: Nielsen Book Data)
 Publisher's Summary
 Limits of Computation: An Introduction to the Undecidable and the Intractable offers a gentle introduction to the theory of computational complexity. It explains the difficulties of computation, addressing problems that have no algorithm at all and problems that cannot be solved efficiently. The book enables readers to understand: * What does it mean for a problem to be unsolvable or to be NPcomplete? * What is meant by a computation and what is a general model of a computer? * What does it mean for an algorithm to exist and what kinds of problems have no algorithm? * What problems have algorithms but the algorithm may take centuries to finish? Developed from the authors' course on computational complexity theory, the text is suitable for advanced undergraduate and beginning graduate students without a strong background in theoretical computer science. Each chapter presents the fundamentals, examples, complete proofs of theorems, and a wide range of exercises.
(source: Nielsen Book Data)
Subjects
 Subject
 Computational complexity.
Bibliographic information
 Publication date
 2013
 Copyright date
 2013
 ISBN
 9781439882061 (hardback : acidfree paper)
 1439882061 (hardback : acidfree paper)