| |
| |
| 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 | |