Preface to the First Edition | p. xi |

To the student | p. xi |

To the educator | p. xii |

The first edition | p. xiii |

Feedback to the author | p. xiii |

Acknowledgments | p. xiv |

Preface to the Second Edition | p. xvii |

Introduction | p. 1 |

Automata, Computability, and Complexity | p. 1 |

Complexity theory | p. 2 |

Computability theory | p. 2 |

Automata theory | p. 3 |

Mathematical Notions and Terminology | p. 3 |

Sets | p. 3 |

Sequences and tuples | p. 6 |

Functions and relations | p. 7 |

Graphs | p. 10 |

Strings and languages | p. 13 |

Boolean logic | p. 14 |

Summary of mathematical terms | p. 16 |

Definitions, Theorems, and Proofs | p. 17 |

Finding proofs | p. 17 |

Types of Proof | p. 21 |

Proof by construction | p. 21 |

Proof by contradiction | p. 21 |

Proof by induction | p. 22 |

Exercises, Problems, and Solutions | p. 25 |

Automata and Languages | p. 29 |

Regular Languages | p. 31 |

Finite Automata | p. 31 |

Formal definition of a finite automaton | p. 35 |

Examples of finite automata | p. 37 |

Formal definition of computation | p. 40 |

Designing finite automata | p. 41 |

The regular operations | p. 44 |

Nondeterminism | p. 47 |

Formal definition of a nondeterministic finite automaton | p. 53 |

Equivalence of NFAs and DFAs | p. 54 |

Closure under the regular operations | p. 58 |

Regular Expressions | p. 63 |

Formal definition of a regular expression | p. 64 |

Equivalence with finite automata | p. 66 |

Nonregular Languages | p. 77 |

The pumping lemma for regular languages | p. 77 |

Exercises, Problems, and Solutions | p. 82 |

Context-Free Languages | p. 99 |

Context-free Grammars | p. 100 |

Formal definition of a context-free grammar | p. 102 |

Examples of context-free grammars | p. 103 |

Designing context-free grammars | p. 104 |

Ambiguity | p. 105 |

Chomsky normal form | p. 106 |

Pushdown Automata | p. 109 |

Formal definition of a pushdown automaton | p. 111 |

Examples of pushdown automata | p. 112 |

Equivalence with context-free grammars | p. 115 |

Non-context-free Languages | p. 123 |

The pumping lemma for context-free languages | p. 123 |

Exercises, Problems, and Solutions | p. 128 |

Computability Theory | p. 135 |

The Church-Turing Thesis | p. 137 |

Turing Machines | p. 137 |

Formal definition of a Turing machine | p. 139 |

Examples of Turing machines | p. 142 |

Variants of Turing Machines | p. 148 |

Multitape Turing machines | p. 148 |

Nondeterministic Turing machines | p. 150 |

Enumerators | p. 152 |

Equivalence with other models | p. 153 |

The Definition of Algorithm | p. 154 |

Hilbert's problems | p. 154 |

Terminology for describing Turing machines | p. 156 |

Exercises, Problems, and Solutions | p. 159 |

Decidability | p. 165 |

Decidable Languages | p. 166 |

Decidable problems concerning regular languages | p. 166 |

Decidable problems concerning context-free languages | p. 170 |

The Halting Problem | p. 173 |

The diagonalization method | p. 174 |

The halting problem is undecidable | p. 179 |

A Turing-unrecognizable language | p. 181 |

Exercises, Problems, and Solutions | p. 182 |

Reducibility | p. 187 |

Undecidable Problems from Language Theory | p. 188 |

Reductions via computation histories | p. 192 |

A Simple Undecidable Problem | p. 199 |

Mapping Reducibility | p. 206 |

Computable functions | p. 206 |

Formal definition of mapping reducibility | p. 207 |

Exercises, Problems, and Solutions | p. 211 |

Advanced Topics in Computability Theory | p. 217 |

The Recursion Theorem | p. 217 |

Self-reference | p. 218 |

Terminology for the recursion theorem | p. 221 |

Applications | p. 222 |

Decidability of logical theories | p. 224 |

A decidable theory | p. 227 |

An undecidable theory | p. 229 |

Turing Reducibility | p. 232 |

A Definition of Information | p. 233 |

Minimal length descriptions | p. 234 |

Optimality of the definition | p. 238 |

Incompressible strings and randomness | p. 239 |

Exercises, Problems, and Solutions | p. 242 |

Complexity Theory | p. 245 |

Time Complexity | p. 247 |

Measuring Complexity | p. 247 |

Big-O and small-o notation | p. 248 |

Analyzing algorithms | p. 251 |

Complexity relationships among models | p. 254 |

The Class P | p. 256 |

Polynomial time | p. 256 |

Examples of problems in P | p. 258 |

The Class NP | p. 264 |

Examples of problems in NP | p. 267 |

The P versus NP question | p. 269 |

NP-completeness | p. 271 |

Polynomial time reducibility | p. 272 |

Definition of NP-completeness | p. 276 |

The Cook-Levin Theorem | p. 276 |

Additional NP-complete Problems | p. 283 |

The vertex cover problem | p. 284 |

The Hamiltonian path problem | p. 286 |

The subset sum problem | p. 291 |

Exercises, Problems, and Solutions | p. 294 |

Space Complexity | p. 303 |

Savitch's Theorem | p. 305 |

The Class PSPACE | p. 308 |

PSPACE-completeness | p. 309 |

The TQBF problem | p. 310 |

Winning strategies for games | p. 313 |

Generalized geography | p. 315 |

The Classes L and NL | p. 320 |

NL-completeness | p. 323 |

Searching in graphs | p. 325 |

NL equals coNL | p. 326 |

Exercises, Problems, and Solutions | p. 328 |

Intractability | p. 335 |

Hierarchy Theorems | p. 336 |

Exponential space completeness | p. 343 |

Relativization | p. 348 |

Limits of the diagonalization method | p. 349 |

Circuit Complexity | p. 351 |

Exercises, Problems, and Solutions | p. 360 |

Advanced topics in complexity theory | p. 365 |

Approximation Algorithms | p. 365 |

Probabilistic Algorithms | p. 368 |

The class BPP | p. 368 |

Primality | p. 371 |

Read-once branching programs | p. 376 |

Alternation | p. 380 |

Alternating time and space | p. 381 |

The Polynomial time hierarchy | p. 386 |

Interactive Proof Systems | p. 387 |

Graph nonisomorphism | p. 387 |

Definition of the model | p. 388 |

IP = PSPACE | p. 390 |

Parallel Computation | p. 399 |

Uniform Boolean circuits | p. 400 |

The class NC | p. 402 |

P-completeness | p. 404 |

Cryptography | p. 405 |

Secret keys | p. 405 |

Public-key cryptosystems | p. 407 |

One-way functions | p. 407 |

Trapdoor functions | p. 409 |

Exercises, Problems, and Solutions | p. 411 |

Selected Bibliography | p. 415 |

Table of Contents provided by Ingram. All Rights Reserved. |