Computability and Complexity Theory
Steven Homer and Alan L. Selman
Springer Verlag New York, 2011
ISBN 9781461406815
View this page in:
This revised and expanded edition of Computability and Complexity Theory
comprises essential materials that are the core knowledge in the theory of
computation. The book is selfcontained, with a preliminary
chapter describing key
mathematical concepts and notations and subsequent chapters moving from the
qualitative aspects of classical computability theory to the
quantitative aspects of
complexity theory. Dedicated chapters on undecidability,
NPcompleteness, and relative
computability round off the work, which focuses on the limitations of computability and
the distinctions between feasible and intractable.
Substantial new content in this edition includes:
*a chapter on nonuniformity studying Boolean circuits, advice classes and the important result of
KarpLipton
*definitions and properties of fundamental probabilistic complexity classes
*a study of the alternating Turing machine and uniform circuit classes
*an introduction to counting classes including the results of Valiant and Vazirani and of Toda
*a thorough treatment of the proof that IP is identical to PSPACE
Topics and features:
*Concise, focused materials cover the most fundamental concepts and
results in the field of modern complexity theory, including the theory of
NPcompleteness, NPhardness, the polynomial hierarchy, and complete
problems for other complexity classes
*Contains information that otherwise exists only in research literature
and presents it in a unified, simplified manner; for example, about
complements of complexity classes, search problems, and intermediate
problems in NP
*Provides key mathematical background information, including sections
on logic and number theory and algebra
*Supported by numerous exercises and supplementary problems for
reinforcement and selfstudy purposes
With its accessibility and welldevised organization, this
text/reference is an excellent resource and guide for those looking to
develop a solid grounding in the theory of computing. Beginning graduates,
advanced undergraduates, and professionals involved in theoretical
computer science, complexity theory, and computability will find the book
an essential and practical learning tool.
Table of Contents
 PRELIMINARIES
 Words and Languages
 Kadic Representation
 Partial Functions
 Graphs
 Propositional Logic
 Cardinality
 Elementary Algebra
 INTRODUCTION TO COMPUTABILITY
 Turing Machines
 TuringMachine Concepts
 Variations of Turing Machines
 Church’s Thesis
 RAMs
 UNDECIDABILITY
 Decision Problems
 Undecidable Problems
 Pairing Functions
 Computably Enumerable Sets
 Halting Problem, Reductions, and Complete Sets
 Smn Theorem
 Recursion Theorem
 Rice’s Theorem
 Turing Reductions and Oracle Turing Machines
 Recursion Theorem, Continued
 References
 Additional Homework Problems
 INTRODUCTION TO COMPLEXITY THEORY
 Complexity Classes and Complexity Measures
 Prerequisites
 BASIC RESULTS OF COMPLEXITY THEORY
 Linear Compression and Speedup
 Constructible Functions
 Tape Reduction
 Inclusion Relationships
 Relations between the Standard Classes
 Separation Results
 Translation Techniques and Padding
 Relations between the Standard ClassesContinued
 Complements of Complexity Classes:
The ImmermanSzelepcsenyi Theorem
 Additional Homework Problems
 NONDETERMINISM AND NPCOMPLETENESS
 Characterizing NP
 The Class P
 Enumerations
 NPCompleteness
 The CookLevin Theorem
 More NPComplete Problems
 Additional Homework Problems
 RELATIVE COMPUTABILITY
 NPHardness
 Search Problems
 The Structure of NP
 Composite Number and Graph Isomorphism
 Reflection
 The Polynomial Hierarchy
 Complete Problems for Other Complexity Classes
 Additional Homework Problems
 NONUNIFORM COMPLEXITY
 Polynomial Size Families of Circuits

 The Low and High Hierarchies


 PARALLELISM
 Alternating Turing Machines
 Uniform Families of Circuits
 Highly Parallelizable Problems
 Uniformity Conditions
 Alternating Turing Machines
 PROBABILISTIC COMPLEXITY CLASSES
 The Class PP
 The Class RP
 The Class BPP
 Randomly Chosen Hash Functions
 The Graph Isomorphism Problem
 Additional Homework Problems
 INTRODUCTION TO COUNTING CLASSES
 Unique Satisfiability
 Toda's Theorem
 Results on BPP and $\oplu$ P
 Additional Homework Problems
 INTERACTIVE PROOF SYSTEMS
 The Formal Model
 The Graph NonIsomorphism Problem
 ArthurMerlin Games
 IP is included in PSPACE
 PSPACE Is Included in IP
 Additional Homework Problems
Front matter with Preface and Table of Contents
[postscript]
[PDF]
Important Links:
Alan Selman