[Proof Complexity] Book announcement: Computability and Complexity

Hubie Chen hubertmingchen at gmail.com
Wed Sep 27 12:18:54 CEST 2023

--- Book announcement ---

"Computability and Complexity"
written by Hubie Chen
published by The MIT Press (year 2023; 416 pages)

* Publisher website for book:

* 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:

* 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

    - 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

Numerous exercises and notes expand upon the main presentation and cover
topics such as Gödel incompleteness, counting complexity, logarithmic space
complexity, and treewidth.

More information about the Proof-Complexity mailing list