| Preface to the First Edition |
| To the student |
| To the educator |
| The first edition |
| Feedback to the author |
| Acknowledgments |
| Preface to the Second 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 |
| 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 |
| The Halting Problem / 4.2： |
| The diagonalization method |
| The halting problem is undecidable |
| 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 |
| 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 |
| Preface to the First Edition |
| To the student |
| To the educator |
図書
