Limits of computation : an introduction to the undecidable and the intractable
- Edna E. Reiter, Clayton Matthew Johnson.
- Boca Raton, FL : CRC Press, Taylor & Francis Group, 
- Copyright notice
- Physical description
- xix, 259 pages ; 24 cm
Math & Statistics Library
|QA267.7 .R445 2013||Unknown|
- Includes bibliographical references (pages 253-254) and index.
- Set Theory Sets-Basic 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? Turing-Completeness Other Versions of Turing Machines Turing Machines to Evaluate a Function E numerating Turing Machines The Church-Turing Thesis A Simple Computer Encodings of Turing Machines Universal Turing Machine Undecidability Introduction and Overview Self-Reference and Self-Contradiction 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 Super-Theorem) Undecidability: What Does It Mean? Post Correspondence Problem Context-Free Grammars Classes NP and NP-Complete The Class NP (Nondeterministic Polynomial) Definition of P and NP Polynomial Reducibility Properties Completeness Intractable and Tractable-Once Again A First NP-Complete Problem: Boolean Satisfiability Cook-Levin Theorem: Proof Conclusion More NP-Complete Problems Adding Other Problems to the List of Known NP-Complete Problems Reductions to Prove NP-Completeness Graph Problems Vertex Cover: The First Graph Problem Other Graph Problems Hamiltonian Circuit (HC) Eulerian Circuits (an Interesting Problem in P) Three-Dimensional 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 NP-P But Not NP-Complete? PSPACE Reachable Configurations NPSPACE = PSPACE A PSPACE Complete Problem Other PSPACE-Complete 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 NP-complete? * 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)
- Computational complexity.
- Publication date
- Copyright date
- 9781439882061 (hardback : acid-free paper)
- 1439882061 (hardback : acid-free paper)
Browse related items
Start at call number: