Preface
To the student
To the educator
The current edition
Feedback to the author
Acknowledgments
0 Introduction
0. l Automata, Computability, and Complexity
Complexity theory
Computability theory
Automata theory
0.2 Mathematical Notions and Terminology
Sets
Sequences and tuples
Functions and relations
Graphs
Strings and languages
Boolean logic
Summary of mathematical terms
O.3 Definitions, Theorems, and Proofs
Finding proofs
0.4 Types of Proof
Proof by construction
Proof by contradiction
Proof by induction
Exercises and Problems
Part One: Automata and
l Regular
l . l Finite Automata
Formal definition of a finite automaton
Examples of finite automata
Formal definition of computation
Designing finite automata
The regular operations
l .2 Nondeterminism
Formal definition of a nondeterministic finite automaton
Equivalence of NFAs and DFAs
Closure under the regular operations
l . 3 Regular Expressions
Formal definition of a regular expression
Equivalence with finite automata
l .4 Nonregular Languages
The pumping lemma for regular languages
Exercises and Problems
2 Context-Free Languages
2 . l Context-free Grammars
Formal definition of a context-free grammar
Examples of context-free grammars
Designing context-free grammars
Ambiguity
Chomsky normal form
2 .2 Pushdown Automata
Formal definition of a pushdown automaton
Examples of pushdown automata
Equivalence with context-free grammars
2 . 3 Non-context-free Languages
The pumping lemma for context-free languages
Exercises and Problems
Part Two: Computability Theory
3 The Church-Turing Thesis
3 . l Turing Machines
Formal definition of a Turing machine
Examples of Turing machines
3 .2 Variants of Turing Machines
Multitape Turing machines
Nondeterministic Turing machines
Enumerators
Equivalence with other models
3 .3 The Definition of Algorithm
Hilbert's problems
Terminology for describing Turing machines
Exercises and Problems
4 Decidability
4. l Decidable Languages
Decidable problems concerning regular languages
Decidable problems concerning context-free languages
4.2 The Halting Problem
The diagonalization method
The halting problem is undecidable
A Turing-unrecognizable language
Exercises and Problems
5 Reducibility
5 . l Undecidable Problems from Language Theory
Reductions via computation histories
5.2 A Simple Undecidable Problem
5 . 3 Mapping Reducibility
Computable functions
Formal definition of mapping reducibility
Exercises and Problems
6 Advanced Topics in Computability Theory
6. 1 The Recursion Theorem
Self-reference
Terminology for the recursion theorem
Applications
6.2 Decidability of logical theories
A decidable theory
An undecidable theory
6. 3 Turing Reducibility
6.4 A Definition of Information
Minimal length descriptions
Optimality of the definition
Incompressible Strings and randomness
Exercises and Problems
Part Three: Complexity Theory
7 Time Complexity
7. l Measuring Complexity
Big-O and small-o notation
Analyzing algorithms
Complexity relationships among models
7.2 The Class P
Polynomial time
Examples of problems in P
7.3 The Class NP
Examples of problems in NP
The P versus NP question
7 .4 NP-completeness
Polynomial time reducibility
Definition of NP-completeness
The Cook-Levin Theorem
7. 5 Additional NP-complete Problems
The vertex cover problem
The Hamiltonian path problem
The subset sum problem
Exercises and Problems
8 Space Complexity
8. l Savitch's Theorem
8.2 The Class PSPACE
8 . 3 PSPACE-completeness
The TQBF problem
Winning strategies for games
Generalized geography
8.4 The Classes Land NL
8. 5 NL-completeness
Searching in graphs
8.6 NL equals coNL
Exercises and Problems
9 Intractability
9. l Hierarchy Theorems
Exponential space completeness
9.2 Relativization
Limits of the diagonalization method
9. 3 Circuit Complexity
Exercises and Problems
10 Advanced topics in complexity theory
l0. l Approximation Algorithms
l0.2 Probabilistic Algorithms
The class BPP
Primality
Read-once branching programs
10.3 Alternation
Alternating time and space
The Polynomial time hierarchy
10.4 Interactive Proof Systems
Graph nonisomorphism
Definition of the model
IP = PSPACE
l0.5 Parallel Compuation
Uniform Boolean circuits
The class NC
P-completeness
IO.6 Cryptography
Secret keys
Public-key cryptosystems
One-way functions
Trapdoor functions
Exercises and Problems
Selected Bibliography
Index
鄂公网安备 42010302001612号 