| |
| |
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 | |
| |
| |
| |
Automata, Computability, and Complexity | |
| |
| |
Complexity theory | |
| |
| |
Computability theory | |
| |
| |
Automata theory | |
| |
| |
| |
Mathematical Notions and Terminology | |
| |
| |
Sets | |
| |
| |
Sequences and tuples | |
| |
| |
Functions and relations | |
| |
| |
Graphs | |
| |
| |
Strings and languages | |
| |
| |
Boolean logic | |
| |
| |
Summary of mathematical terms | |
| |
| |
| |
Definitions, Theorems, and Proofs | |
| |
| |
Finding proofs | |
| |
| |
| |
Types of Proof | |
| |
| |
Proof by construction | |
| |
| |
Proof by contradiction | |
| |
| |
Proof by induction | |
| |
| |
Exercises, Problems, and Solutions | |
| |
| |
| |
Automata and Languages | |
| |
| |
| |
Regular Languages | |
| |
| |
| |
Finite Automata | |
| |
| |
Formal definition of a finite automaton | |
| |
| |
Examples of finite automata | |
| |
| |
Formal definition of computation | |
| |
| |
Designing finite automata | |
| |
| |
The regular operations | |
| |
| |
| |
Nondeterminism | |
| |
| |
Formal definition of a nondeterministic finite automaton | |
| |
| |
Equivalence of NFAs and DFAs | |
| |
| |
Closure under the regular operations | |
| |
| |
| |
Regular Expressions | |
| |
| |
Formal definition of a regular expression | |
| |
| |
Equivalence with finite automata | |
| |
| |
| |
Nonregular Languages | |
| |
| |
The pumping lemma for regular languages | |
| |
| |
Exercises, Problems, and Solutions | |
| |
| |
| |
Context-Free Languages | |
| |
| |
| |
Context-free Grammars | |
| |
| |
Formal definition of a context-free grammar | |
| |
| |
Examples of context-free grammars | |
| |
| |
Designing context-free grammars | |
| |
| |
Ambiguity | |
| |
| |
Chomsky normal form | |
| |
| |
| |
Pushdown Automata | |
| |
| |
Formal definition of a pushdown automaton | |
| |
| |
Examples of pushdown automata | |
| |
| |
Equivalence with context-free grammars | |
| |
| |
| |
Non-context-free Languages | |
| |
| |
The pumping lemma for context-free languages | |
| |
| |
Exercises, Problems, and Solutions | |
| |
| |
| |
Computability Theory | |
| |
| |
| |
The Church-Turing Thesis | |
| |
| |
| |
Turing Machines | |
| |
| |
Formal definition of a Turing machine | |
| |
| |
Examples of Turing machines | |
| |
| |
| |
Variants of Turing Machines | |
| |
| |
Multitape Turing machines | |
| |
| |
Nondeterministic Turing machines | |
| |
| |
Enumerators | |
| |
| |
Equivalence with other models | |
| |
| |
| |
The Definition of Algorithm | |
| |
| |
Hilbert's problems | |
| |
| |
Terminology for describing Turing machines | |
| |
| |
Exercises, Problems, and Solutions | |
| |
| |
| |
Decidability | |
| |
| |
| |
Decidable Languages | |
| |
| |
Decidable problems concerning regular languages | |
| |
| |
Decidable problems concerning context-free languages | |
| |
| |
| |
The Halting Problem | |
| |
| |
The diagonalization method | |
| |
| |
The halting problem is undecidable | |
| |
| |
A Turing-unrecognizable language | |
| |
| |
Exercises, Problems, and Solutions | |
| |
| |
| |
Reducibility | |
| |
| |
| |
Undecidable Problems from Language Theory | |
| |
| |
Reductions via computation histories | |
| |
| |
| |
A Simple Undecidable Problem | |
| |
| |
| |
Mapping Reducibility | |
| |
| |
Computable functions | |
| |
| |
Formal definition of mapping reducibility | |
| |
| |
Exercises, Problems, and Solutions | |
| |
| |
| |
Advanced Topics in Computability Theory | |
| |
| |
| |
The Recursion Theorem | |
| |
| |
Self-reference | |
| |
| |
Terminology for the recursion theorem | |
| |
| |
Applications | |
| |
| |
| |
Decidability of logical theories | |
| |
| |
A decidable theory | |
| |
| |
An undecidable theory | |
| |
| |
| |
Turing Reducibility | |
| |
| |
| |
A Definition of Information | |
| |
| |
Minimal length descriptions | |
| |
| |
Optimality of the definition | |
| |
| |
Incompressible strings and randomness | |
| |
| |
Exercises, Problems, and Solutions | |
| |
| |
| |
Complexity Theory | |
| |
| |
| |
Time Complexity | |
| |
| |
| |
Measuring Complexity | |
| |
| |
Big-O and small-o notation | |
| |
| |
Analyzing algorithms | |
| |
| |
Complexity relationships among models | |
| |
| |
| |
The Class P | |
| |
| |
Polynomial time | |
| |
| |
Examples of problems in P | |
| |
| |
| |
The Class NP | |
| |
| |
Examples of problems in NP | |
| |
| |
The P versus NP question | |
| |
| |
| |
NP-completeness | |
| |
| |
Polynomial time reducibility | |
| |
| |
Definition of NP-completeness | |
| |
| |
The Cook-Levin Theorem | |
| |
| |
| |
Additional NP-complete Problems | |
| |
| |
The vertex cover problem | |
| |
| |
The Hamiltonian path problem | |
| |
| |
The subset sum problem | |
| |
| |
Exercises, Problems, and Solutions | |
| |
| |
| |
Space Complexity | |
| |
| |
| |
Savitch's Theorem | |
| |
| |
| |
The Class PSPACE | |
| |
| |
| |
PSPACE-completeness | |
| |
| |
The TQBF problem | |
| |
| |
Winning strategies for games | |
| |
| |
Generalized geography | |
| |
| |
| |
The Classes L and NL | |
| |
| |
| |
NL-completeness | |
| |
| |
Searching in graphs | |
| |
| |
| |
NL equals coNL | |
| |
| |
Exercises, Problems, and Solutions | |
| |
| |
| |
Intractability | |
| |
| |
| |
Hierarchy Theorems | |
| |
| |
Exponential space completeness | |
| |
| |
| |
Relativization | |
| |
| |
Limits of the diagonalization method | |
| |
| |
| |
Circuit Complexity | |
| |
| |
Exercises, Problems, and Solutions | |
| |
| |
| |
Advanced topics in complexity theory | |
| |
| |
| |
Approximation Algorithms | |
| |
| |
| |
Probabilistic Algorithms | |
| |
| |
The class BPP | |
| |
| |
Primality | |
| |
| |
Read-once branching programs | |
| |
| |
| |
Alternation | |
| |
| |
Alternating time and space | |
| |
| |
The Polynomial time hierarchy | |
| |
| |
| |
Interactive Proof Systems | |
| |
| |
Graph nonisomorphism | |
| |
| |
Definition of the model | |
| |
| |
IP = PSPACE | |
| |
| |
| |
Parallel Computation | |
| |
| |
Uniform Boolean circuits | |
| |
| |
The class NC | |
| |
| |
P-completeness | |
| |
| |
| |
Cryptography | |
| |
| |
Secret keys | |
| |
| |
Public-key cryptosystems | |
| |
| |
One-way functions | |
| |
| |
Trapdoor functions | |
| |
| |
Exercises, Problems, and Solutions | |
| |
| |
Selected Bibliography | |