Theory of Computational Complexity Book

	Preface	ix
Part I	Uniform Complexity	1
1	Models of Computation and Complexity Classes	3
1.1	Strings, Coding, and Boolean Functions	3
1.2	Deterministic Turing Machines	7
1.3	Nondeterministic Turing Machines	14
1.4	Complexity Classes	18
1.5	Universal Turing Machine	24
1.6	Diagonalization	27
1.7	Simulation	31
	Exercises	36
	Historical Notes	42
2	NP-Completeness	43
2.1	NP	43
2.2	Cook's Theorem	47
2.3	More NP-Complete Problems	51
2.4	Polynomial-Time Turing Reducibility	58
2.5	NP-Complete Optimization Problems	64
	Exercises	71
	Historical Notes	75
3	The Polynomial-Time Hierarchy and Polynomial Space	77
3.1	Nondeterministic Oracle Turing Machines	77
3.2	Polynomial-Time Hierarchy	79
3.3	Complete Problems in PH	84
3.4	Alternating Turing Machines	90
3.5	PSPACE-Complete Problems	95
3.6	EXP-Complete Problems	102
	Exercises	108
	Historical Notes	111
4	Structure of NP	113
4.1	Incomplete Problems in NP	113
4.2	One-Way Functions and Cryptography	119
4.3	Relativization	125
4.4	Unrelativizable Proof Techniques	127
4.5	Independence Results	127
4.6	Positive Relativization	129
4.7	Random Oracles	131
4.8	Structure of Relativized NP	135
	Exercises	139
	Historical Notes	143
Part II	Nonuniform Complexity	145
5	Decision Trees	147
5.1	Graphs and Decision Trees	147
5.2	Examples	153
5.3	Algebraic Criterion	157
5.4	Monotone Graph Properties	161
5.5	Topological Criterion	163
5.6	Applications of the Fixed Point Theorems	170
5.7	Applications of Permutation Groups	173
5.8	Randomized Decision Trees	176
5.9	Branching Programs	181
	Exercises	188
	Historical Notes	192
6	Circuit Complexity	195
6.1	Boolean Circuits	195
6.2	Polynomial-Size Circuits	199
6.3	Monotone Circuits	205
6.4	Circuits with Modulo Gates	213
6.5	NC	216
6.6	Parity Function	221
6.7	P-Completeness	229
6.8	Random Circuits and RNC	234
	Exercises	238
	Historical Notes	242
7	Polynomial-Time Isomorphism	245
7.1	Polynomial-Time Isomorphism	245
7.2	Paddability	249
7.3	Density of NP-Complete Sets	254
7.4	Density of EXP-Complete Sets	262
7.5	One-Way Functions and Isomorphism in EXP	266
7.6	Density of P-Complete Sets	276
	Exercises	280
	Historical Notes	283
Part III	Probabilistic Complexity	285
8	Probabilistic Machines and Complexity Classes	287
8.1	Randomized Algorithms	287
8.2	Probabilistic Turing Machines	292
8.3	Time Complexity of Probabilistic Turing Machines	295
8.4	Probabilistic Machines with Bounded Errors	298
8.5	BPP and P	301
8.6	BPP and NP	304
8.7	BPP and the Polynomial-Time Hierarchy	306
8.8	Relativized Probabilistic Complexity Classes	310
	Exercises	315
	Historical Notes	319
9	Complexity of Counting	321
9.1	Counting Class #P	322
9.2	#P-Complete Problems	325
9.3	[plus sign in circle]P and the Polynomial-Time Hierarchy	334
9.4	#P and the Polynomial-Time Hierarchy	340
9.5	Circuit Complexity and Relativized [plus sign in circle]P and #P	342
9.6	Relativized Polynomial-Time Hierarchy	346
	Exercises	348
	Historical Notes	351
10	Interactive Proof Systems	353
10.1	Examples and Definitions	353
10.2	Arthur-Merlin Proof Systems	361
10.3	AM Hierarchy Versus Polynomial-Time Hierarchy	365
10.4	IP Versus AM	372
10.5	IP Versus PSPACE	382
	Exercises	387
	Historical Notes	390
11	Probabilistically Checkable Proofs and NP-Hard Optimization Problems	393
11.1	Probabilistically Checkable Proofs	393
11.2	PCP Characterization of Nondeterministic Exponential Time	396
11.2.1	Proof	397
11.2.2	Multilinearity Test System	403
11.2.3	Sum Check System	408
11.3	PCP Characterization of NP	410
11.3.1	Proof System for NP Using O(log n) Random Bits	412
11.3.2	Low-Degree Test System	416
11.3.3	Composition of Two PCP Systems	419
11.3.4	Proof System Reading a Constant Number of Oracle Bits	424
11.4	Probabilistic Checking and Nonapproximability	430
11.5	More NP-Hard Approximation Problems	434
	Exercises	446
	Historical Notes	450
	Bibliography	453
	Index	475