Computability and complexity theory. (Q640476)

This book is intended to serve as a textbook for an introductory graduate course in theoretical computer science. According to the conviction of the authors that the important topics to teach at this level are the fundamental models of computation, the limits of computation, and the distinction between feasible and intractible, the different chapters of the book cover Turing machines and Church's thesis, undecidability, complexity measures and relations among them, nondeterminism and NP-completeness, relative computability, nonuniform complexity, parallelism and uniform circuit families, probabilistic classes, counting classes, and interactive proof systems. With this diverse spectrum of topics the book is even suitable as a text for a two semester graduate course. Though the topics are treated in depth and not only surveyed, they address all graduate students, not only those that will specialize in complexity. The book provides a solid background for the latter group that will have to consult further textbooks for more specialized topics on, e.g., circuit complexity, descriptive complexity, the PCP theorem, etc.