Computability and Complexity Theory, 2nd Edition

This textbook is intended for use in an introductory graduate course in theoretical computer science. The book presents core knowledge in the theory of computation for all graduate students in computer science. This self-contained reference is best suited for a one semester course, covered in one semester by moving expeditiously through the core material of Chapters 1 through 5 and then covering parts of Chapter 6. The text begins with classical computability theory and builds complexity theory on top of that foundation, thus enabling students to learn a qualitative subject before advancing to a quantitative one. In addition, the concepts build from one to the next. This new edition contains additional chapters on nonuniform complexity, circuit complexity and parallel complexity, and randomized complexity.

Table of Contents

Chapter 1 Preliminaries
Chapter 2 Introduction to Computability
Chapter 3 Undecidability
Chapter 4 Introduction to Complexity Theory
Chapter 5 Basic Results of Complexity Theory
Chapter 6 Nondeterminism and NP-Completeness
Chapter 7 Relative Computability
Chapter 8 Nonuniform Complexity
Chapter 9 Parallelism
Chapter 10 Probabilistic Complexity Classes
Chapter 11 Introduction to Counting Classes
Chapter 12 Interactive Proof Systems