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