"Computability and Complexity"
written by Hubie Chen
published by The MIT Press (year 2023; 416 pages)
* 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/14340/CC_Book_selection.pdf
.
* 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, fixed-parameter tractability, 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.
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
