0 Introduction 1
0.1 Automata,Computability,and Complexity 1
Complexity theory 2
Computability theory 2
Automata theory 3
0.2 Mathematical Notions and Terminology 3
Sets 3
Sequences and tuples 6
Functions and relations 7
Graphs 10
Strings and languages 13
Boolean logic 14
Summary of mathematical terms 16
0.3 Definitions,Theorems,and Proofs 17
Finding proofs 17
0.4 Types of Proof 21
Proof by construction 21
Proof by contradiction 21
Proof by induction 23
Exercises and Problems 25
Part One:Automata and Languages 29
1 Regular Languages 31
1.1 Finite Automata 31
Formal definition of a finite automaton 35
Examples of finite automata 37
Formal definition of computation 40
Designing finite automata 41
The regular operations 44
1.2 Nondeterminism 47
Formal definition of a nondeterministic finite automaton 53
Equivalence of NFAs and DFAs 54
Closure under the regular operations 58
1.3 Regular Expressions 63
Formal definition ofa regular expression 64
Equivalence with finite automata 66
1.4 Nonregular Languages 77
Thepumping lemma for regular languages 77
Exercises and Problems 83
2 Context-Free Languages 91
2.1 Context-free Grammars 92
Formal definition of a context-free grammar 94
Examples of context-free grammars 95
Designing context-free grammars 96
Ambiguity 97
Chomsky normal form 98
2.2 Pushdown Automata 101
Formal definition of a pushdown automaton 103
Examples of pushdown automata 104
Equivalence with context-free grammars 106
The pumping lemma for context-free languages 115
2.3 Non-context-free Languages 115
Exercises and Problems 119
Part Two：Computability Theory 123
3 The Church-Turing Thesis 125
3.1 Turing Machines 125
Formal definition of a Turing machine 127
Examples of Turing machines 130
3.2 Variants of Turing Machines 136
Multitape Turing machines 136
Nondeterministic Turing machines 138
Enumerators 140
Equivalence with other models 141
3.3 The Definition of Algorithm 142
Hilbert's problems 142
Terminology for describing Turing machines 144
Exercises and Problems 147
4 Decidability 151
4.1 Decidable Languages 152
Decidable problems concerning regular languages 152
Decidable problems concerning context-free languages 156
4.2 The Halting Problem 159
The diagonalization method 160
The halting problem is undecidable 165
ATuring-unrecognizable language 167
Exercises and Problems 168
5 Reducibility 171
5.1 Undecidable Problems from Language Theory 172
Reductions via computation histories 176
5.2 A Simple Undecidable Problem 183
5.3 Mapping Reducibility 189
Computable functions 190
Formal definition ofmapping reducibility 191
Exercises and Problems 195
6 Advanced Topics in Computability Theory 197
6.1 The Recursion Theorem 197
Self-reference 198
Terminology for the recursion theorem 201
Applications 202
6.2 Decidability of logical theories 204
A decidable theory 206
An undecidable theory 209
6.3 Turing Reducibility 211
6.4 A Definition of Information 213
Minimal length descriptions 214
Optimality of the definition 217
Incompressible strings and randomness 217
Exercises and Problems 220
Part Three:Complexity Theory 223
7 Time Complexity 225
7.1 Measuring Complexity 225
Big-O and small-o notation 226
Analyzing algorithms 229
Complexity relationships among models 231
7.2 The Class P 234
Polynomial time 234
Examples of problems in P 236
7.3 The Class NP 241
Examples of problemsin NP 245
The P versus NP question 247
7.4 NP-completeness 248
Polynomial time reducibility 249
Definition of NP-completeness 253
The Cook-Levin Theorem 254
7.5 Additional NP-complete Problems 260
The vertex cover problem 261
The Hamiltonian path problem 262
The subset sum problem 268
Exercises and Problems 271
8 Space Complexity 277
8.1 Savitch's Theorem 279
8.2 The Class PSPACE 281
The TQBF problem 283
8.3 PSPACE-completeness 283
Winning strategies for games 287
Generalized geography 289
8.4 The Classes L and NL 294
8.5 NL-completeness 297
Searching in graphs 298
8.6 NL equals coNL 300
Exercises and Problems 302
9 Intractability 305
9.1 Hierarchy Theorems 306
Exponential space completeness 313
9.2 Relativization 318
Limits of the diagonalization method 319
9.3 Circuit Complexity 321
Exercises and Problems 330
10 Advanced topics in complexity theory 333
10.1 Approximation Algorithms 333
10.2 Probabilistic Algorithms 335
The class BPP 336
Primality 339
Read-once branching programs 343
10.3 Alternation 348
Alternating time and space 349
The Polynomial time hierarchy 353
10.4 Interactive Proof Systems 354
Graph nonisomorphism 355
Definition of the model 355
IP=PSPACE 357
10.5 Parallel Computation 366
Uniform Boolean circuits 367
The class NC 369
P-completeness 371
10.6 Cryptography 372
Secret keys 372
Public-key cryptosystems 374
One-way functions 374
Trapdoor functions 376
Exercises and Problems 378
Selected Bibliography 381
Index 387