Computability and complexity theory. (Q640476)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Computability and complexity theory. |
scientific article |
Statements
Computability and complexity theory. (English)
0 references
18 October 2011
0 references
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.
0 references
computability
0 references
Turing machine
0 references
computational complexity
0 references
decidability
0 references
randomness
0 references
counting complexity
0 references
interactive proof
0 references