| |

| |

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