--- Book announcement ---
"Computability and Complexity" written by Hubie Chen published by The MIT Press
* Publisher website for book: https://mitpress.mit.edu/9780262048620/computability-and-complexity/
* Book excerpt:
An excerpt of this book, which includes the first chapter (of 4), is freely useable and freely distributable under a Creative Commons CC-BY-NC-ND license. See the above website or use a direct link: https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/1434... .
* Description:
This initiation to the theory of computation covers the core notions, techniques, methods, and questions of this theory, before turning to several advanced topics. This book combines intuitive and conceptual discussion—--backed by numerous diagrams and examples—--with a precise mathematical treatment that includes comprehensive and rigorous proofs.
Topics covered by this book include:
- Automata theory – deterministic and nondeterministic finite automata, regular expressions, proving non-regularity via Myhill-Nerode theory, DFA minimization;
- Computability theory – deterministic and nondeterministic Turing machines, universal Turing machines, diagonalization and non-computable languages, reductions, Rice’s theorem;
- Complexity theory – time complexity classes (P, NP, and coNP), the P versus NP question, the theories of NP-completeness and of coNP-completeness, numerous completeness proofs, the space complexity class PSPACE, hierarchy theorems, parameterized complexity.
Numerous exercises and notes expand upon the main presentation and cover topics such as Gödel incompleteness, counting complexity, logarithmic space complexity, and treewidth.