Preface to the First Edition |
To the student |
To the educator |
The first edition |
Feedback to the author |
Acknowledgments |
Preface to the Second Edition |
Preface to the Third Edition |
Introduction / 0: |
Automata, Computability, and Complexity / 0.1: |
Complexity theory |
Computability theory |
Automata theory |
Mathematical Notions and Terminology / 0.2: |
Sets |
Sequences and tuples |
Functions and relations |
Graphs |
Strings and languages |
Boolean logic |
Summary of mathematical terms |
Definitions, Theorems, and Proofs / 0.3: |
Finding proofs |
Types of Proof / 0.4: |
Proof by construction |
Proof by contradiction |
Proof by induction |
Exercises, Problems, and Solutions |
Automata and Languages / Part 1: |
Regular Languages / 1: |
Finite Automata / 1.1: |
Formal definition of a finite automaton |
Examples of finite automata |
Formal definition of computation |
Designing finite automata |
The regular operations |
Nondeterminism / 1.2: |
Formal definition of a nondeterministic finite automaton |
Equivalence of NFAs and DFAs |
Closure under the regular operations |
Regular Expressions / 1.3: |
Formal definition of a regular expression |
Equivalence with finite automata |
Nonregular Languages / 1.4: |
The pumping lemma for regular languages |
Context-Free Languages / 2: |
Context-Free Grammars / 2.1: |
Formal definition of a context-free grammar |
Examples of context-free grammars |
Designing context-free grammars |
Ambiguity |
Chomsky normal form |
Pushdown Automata / 2.2: |
Formal definition of a pushdown automaton |
Examples of pushdown automata |
Equivalence with context-free grammars |
Non-Context-Free Languages / 2.3: |
The pumping lemma for context-free languages |
Deterministic Context-Free Languages / 2.4: |
Properties of DCFLs |
Deterministic context-free grammars |
Relationship of DPDAs and DCFGs |
Parsing and LR(k) Grammars |
Computability Theory / Part 2: |
The Church-Turing Thesis / 3: |
Turing Machines / 3.1: |
Formal definition of a Turing machine |
Examples of Turing machines |
Variants of Turing Machines / 3.2: |
Multitape Turing machines |
Nondeterministic Turing machines |
Enumerators |
Equivalence with other models |
The Definition of Algorithm / 3.3: |
Hilbert's problems |
Terminology for describing Turing machines |
Decidability / 4: |
Decidable Languages / 4.1: |
Decidable problems concerning regular languages |
Decidable problems concerning context-free languages |
Undecidability / 4.2: |
The diagonalization method |
An undecidable language |
A Turing-unrecognizable language |
Reducibility / 5: |
Undecidable Problems from Language Theory / 5.1: |
Reductions via computation histories |
A Simple Undecidable Problem / 5.2: |
Mapping Reducibility / 5.3: |
Computable functions |
Formal definition of mapping reducibility |
Advanced Topics in Computability Theory / 6: |
The Recursion Theorem / 6.1: |
Self-reference |
Terminology for the recursion theorem |
Applications |
Decidability of logical theories / 6.2: |
A decidable theory |
An undecidable theory |
Turing Reducibility / 6.3: |
A Definition of Information / 6.4: |
Minimal length descriptions |
Optimality of the definition |
Incompressible strings and randomness |
Complexity Theory / Part 3: |
Time Complexity / 7: |
Measuring Complexity / 7.1: |
Big-O and small-o notation |
Analyzing algorithms |
Complexity relationships among models |
The Class P / 7.2: |
Polynomial time |
Examples of problems in P |
The Class NP / 7.3: |
Examples of problems in NP |
The P versus NP question |
NP-completeness / 7.4: |
Polynomial time reducibility |
Definition of NP-completeness |
The Cook-Levin Theorem |
Additional NP-complete Problems / 7.5: |
The vertex cover problem |
The Hamiltonian path problem |
The subset sum problem |
Exercises, Problems, arid Solutions |
Space Complexity / 8: |
SavitchÆs Theorem / 8.1: |
The Class PSPACE / 8.2: |
PSPACE-completeness / 8.3: |
The TQBF problem |
Winning strategies for games |
Generalized geography |
The Classes L and NL / 8.4: |
NL-completeness / 8.5: |
Searching in graphs |
NL equals coNL / 8.6: |
Intractability / 9: |
Hierarchy Theorems / 9.1: |
Exponential space completeness |
Relativization / 9.2: |
Limits of the diagonalization method |
Circuit Complexity / 9.3: |
Advanced Topics in Complexity Theory / 10: |
Approximation Algorithms / 10.1: |
Probabilistic Algorithms / 10.2: |
The class BPP |
Primality |
Read-once branching programs |
Alternation / 10.3: |
Alternating time and space |
The Polynomial time hierarchy |
Interactive Proof Systems / 10.4: |
Graph nonisomorphism |
Definition of the model |
IP = PSPACE |
Parallel Computation / 10.5: |
Uniform Boolean circuits |
The class NC |
P-completeness |
Cryptography / 10.6: |
Secret keys |
Public-key cryptosystems |
One-way functions |
Trapdoor functions |
Selected Bibliography |
Index |
Preface to the First Edition |
To the student |
To the educator |