Enhanced descriptions from Syndetics:

Michael Sipser's philosophy in writing this book is simple: make the subject interesting and relevant, and the students will learn. His emphasis on unifying computer science theory - rather than offering a collection of low-level details - sets the book apart, as do his intuitive explanations. Throughout the book, Sipser - a noted authority on the theory of computation - builds students' knowledge of conceptual tools used in computer science, the aesthetic sense they need to create elegant systems, and the ability to think through problems on their own. INTRODUCTION TO THE THEORY OF COMPUTATION provides a mathematical treatment of computation theory grounded in theorems and proofs. Proofs are presented with a "proof idea" component to reveal the concepts underpinning the formalism. Algorithms are presented using prose instead of pseudocode to focus attention on the algorithms themselves, rather than on specific computational models. Topic coverage, terminology, and order of presentation are traditional for an upper-level course in computer science theory. Users of the Preliminary Edition (now out of print) will be interested to note several new chapters on complexity theory: Chapter 8 on space complexity; Chapter 9 on provable intractability, and Chapter 10 on advanced topics, including approximation algorithms, alternation, interactive proof systems, cryptography, and parallel computing.

Table of contents provided by Syndetics

• 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)
• 0 Introduction (p. 1)
• 0.1 Automata, Computability, and Complexity (p. 1)
• Complexity theory (p. 2)
• Computability theory (p. 2)
• Automata theory (p. 3)
• 0.2 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)
• 0.3 Definitions, Theorems, and Proofs (p. 17)
• Finding proofs (p. 17)
• 0.4 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)
• Part 1 Automata and Languages (p. 29)
• 1 Regular Languages (p. 31)
• 1.1 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)
• 1.2 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)
• 1.3 Regular Expressions (p. 63)
• Formal definition of a regular expression (p. 64)
• Equivalence with finite automata (p. 66)
• 1.4 Nonregular Languages (p. 77)
• The pumping lemma for regular languages (p. 77)
• Exercises, Problems, and Solutions (p. 82)
• 2 Context-Free Languages (p. 99)
• 2.1 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)
• 2.2 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)
• 2.3 Non-context-free Languages (p. 123)
• The pumping lemma for context-free languages (p. 123)
• Exercises, Problems, and Solutions (p. 128)
• Part 2 Computability Theory (p. 135)
• 3 The Church-Turing Thesis (p. 137)
• 3.1 Turing Machines (p. 137)
• Formal definition of a Turing machine (p. 139)
• Examples of Turing machines (p. 142)
• 3.2 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)
• 3.3 The Definition of Algorithm (p. 154)
• Hilbert's problems (p. 154)
• Terminology for describing Turing machines (p. 156)
• Exercises, Problems, and Solutions (p. 159)
• 4 Decidability (p. 165)
• 4.1 Decidable Languages (p. 166)
• Decidable problems concerning regular languages (p. 166)
• Decidable problems concerning context-free languages (p. 170)
• 4.2 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)
• 5 Reducibility (p. 187)
• 5.1 Undecidable Problems from Language Theory (p. 188)
• Reductions via computation histories (p. 192)
• 5.2 A Simple Undecidable Problem (p. 199)
• 5.3 Mapping Reducibility (p. 206)
• Computable functions (p. 206)
• Formal definition of mapping reducibility (p. 207)
• Exercises, Problems, and Solutions (p. 211)
• 6 Advanced Topics in Computability Theory (p. 217)
• 6.1 The Recursion Theorem (p. 217)
• Self-reference (p. 218)
• Terminology for the recursion theorem (p. 221)
• Applications (p. 222)
• 6.2 Decidability of logical theories (p. 224)
• A decidable theory (p. 227)
• An undecidable theory (p. 229)
• 6.3 Turing Reducibility (p. 232)
• 6.4 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)
• Part 3 Complexity Theory (p. 245)
• 7 Time Complexity (p. 247)
• 7.1 Measuring Complexity (p. 247)
• Big-O and small-o notation (p. 248)
• Analyzing algorithms (p. 251)
• Complexity relationships among models (p. 254)
• 7.2 The Class P (p. 256)
• Polynomial time (p. 256)
• Examples of problems in P (p. 258)
• 7.3 The Class NP (p. 264)
• Examples of problems in NP (p. 267)
• The P versus NP question (p. 269)
• 7.4 NP-completeness (p. 271)
• Polynomial time reducibility (p. 272)
• Definition of NP-completeness (p. 276)
• The Cook-Levin Theorem (p. 276)
• 7.5 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)
• 8 Space Complexity (p. 303)
• 8.1 Savitch's Theorem (p. 305)
• 8.2 The Class PSPACE (p. 308)
• 8.3 PSPACE-completeness (p. 309)
• The TQBF problem (p. 310)
• Winning strategies for games (p. 313)
• Generalized geography (p. 315)
• 8.4 The Classes L and NL (p. 320)
• 8.5 NL-completeness (p. 323)
• Searching in graphs (p. 325)
• 8.6 NL equals coNL (p. 326)
• Exercises, Problems, and Solutions (p. 328)
• 9 Intractability (p. 335)
• 9.1 Hierarchy Theorems (p. 336)
• Exponential space completeness (p. 343)
• 9.2 Relativization (p. 348)
• Limits of the diagonalization method (p. 349)
• 9.3 Circuit Complexity (p. 351)
• Exercises, Problems, and Solutions (p. 360)
• 10 Advanced topics in complexity theory (p. 365)
• 10.1 Approximation Algorithms (p. 365)
• 10.2 Probabilistic Algorithms (p. 368)
• The class BPP (p. 368)
• Primality (p. 371)
• Read-once branching programs (p. 376)
• 10.3 Alternation (p. 380)
• Alternating time and space (p. 381)
• The Polynomial time hierarchy (p. 386)
• 10.4 Interactive Proof Systems (p. 387)
• Graph nonisomorphism (p. 387)
• Definition of the model (p. 388)
• IP = PSPACE (p. 390)
• 10.5 Parallel Computation (p. 399)
• Uniform Boolean circuits (p. 400)
• The class NC (p. 402)
• P-completeness (p. 404)
• 10.6 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)

Author notes provided by Syndetics