Computability and complexity theory (Q5925717)

This textbook is intended for use in a modern graduate course in the theory of computing. The classical computability theory based on Turing machines and Church's thesis is the core of authors approach. The complexity theory is built as a natural way of evaluating computational behavior of algorithms. This theory is represented by undecidability results, space and time hierarchy theorems and detailed description of complexity classes and complexity measures, including classes P and NP. Mainly all old classical complexity results as well as a relatively recent result that space-bounded classes are closed under complements are included into the book. The textbook is self-contained. A list of useful homework problems is appended to each chapter. The book is well written and is recommended to students as well as specialists in theoretical computer science.