The Complexity Theory Companion

Cover......Page 1
Preface......Page 6
Contents......Page 10
1. The Self-Reducibility Technique......Page 14
1.1 GEM There Are No Sparse NP-Complete Sets Unless P=NP......Page 15
1.2 The Turing Case......Page 31
1.3 The Case of Merely Putting Sparse Sets in NP - P The Hartmanis-lmmerman-Sewelson Encoding......Page 35
1.5 Bibliographic Notes......Page 39
2. The One-Way Function Technique......Page 44
2.1 GEM Characterizing the Existence of One-Way Functions......Page 45
2.2 Unambiguous One-Way Functions Exist If and Only If Bounded-Ambiguity One-Way Functions Exist......Page 48
2.3 Strong, Total, Commutative, Associative One-Way Functions Exist If and Only If One-Way Functions Exist......Page 49
2.4 OPEN ISSUE Low-Ambiguity, Commutative, Associative One-Way Functions......Page 55
2.5 Bibliographic Notes......Page 56
3.1 GEM The Semi-feasible Sets Have Small Circuits......Page 58
3.2 Optimal Advice for the Semi-feasible Sets......Page 61
3.3 Unique Solutions Collapse the Polynomial Hierarchy......Page 69
3.5 Bibliographic Notes......Page 76
4. The Isolation Technique......Page 80
4.1 GEM Isolating a Unique Solution......Page 81
4.2 Toda\'s Theorem PH ~ pPP......Page 85
4.3 NLpoly = ULpoly......Page 95
4.5 Bibliographic Notes......Page 100
5.1 Framing the Question: Is P Closed Under Proper Subtraction......Page 104
5.2 GEM: A Complexity Theory for Feasible Closure Properties of #P......Page 106
5.3 Intermediate Potential Closure Properties......Page 112
5.4 A Complexity Theory for Feasible Closure Properties of OptP......Page 116
5.5 OPEN ISSUE: Characterizing Closure Under Proper Decrement......Page 118
5.6 Bibliographic Notes......Page 119
6. The Polynomial Interpolation Technique......Page 122
6.1 GEM: Interactive Protocols for the Permanent......Page 123
6.2 Enumerators for the Permanent......Page 132
6.3 IP = PSPACE......Page 135
6.4 MIP = NEXP......Page 146
6.6 Bibliographic Notes......Page 176
7. The Nonsolvable Group Technique......Page 180
7.1 GEM: Width-5 Branching Programs Capture Nonuniform-NC1......Page 181
7.2 Width-5 Bottleneck Machines Capture PSPACE......Page 189
7.3 Width-2 Bottleneck Computation......Page 194
7.5 Bibliographic Notes......Page 205
8.1 GEM: The Random Restriction Technique and a Polynomial-Size Lower Bound for Parity......Page 210
8.2 An Exponential-Size Lower Bound for Parity......Page 220
8.3 PH and PSPACE Differ with Probability One......Page 231
8.4 Oracles That Make the Polynomial Hierarchy Infinite......Page 235
8.6 Bibliographic Notes......Page 244
9. The Polynomial Technique......Page 248
9.1 GEM: The Polynomial Technique......Page 249
9.2 Closure Properties of PP......Page 254
9.3 The Probabilistic Logspace Hierarchy Collapses......Page 265
9.4 OPEN ISSUE: Is PP Closed Under Polynomial-Time Turing Reductions......Page 272
9.5 Bibliographic Notes......Page 273
A. A Rogues\' Gallery of Complexity Classes......Page 276
A.1 P: Determinism......Page 277
A.2 NP: Nondeterminism......Page 279
A.3 Oracles and Relativized Worlds......Page 281
A.4 The Polynomial Hierarchy and Polynomial Space: The Power of Quantifiers......Page 283
A.6 P /Poly: Small Circuits......Page 289
A.7 L, NL, etc.: Logspace Classes......Page 290
A.8 NC, AC, LOGCFL: Circuit Classes......Page 292
A.9 UP, FewP, and US: Ambiguity-Bounded Computation and Unique Computation......Page 294
A.10 #P: Counting Solutions......Page 299
A.ll ZPP, RP, coRP, and BPP: Error-Bounded Probabilism......Page 301
A.12 PP, C=P, and SPP: Counting Classes......Page 303
A.13 FP, NPSV, and NPMV: Deterministic and Nondeterministic Functions......Page 304
A.14 P-Sel: Semi-feasible Computation......Page 307
A.16 SpanP, OptP: Output-Cardinality and Optimization Function Classes......Page 310
A.17 IP and MIP: Interactive Proof Classes......Page 312
A.18 PBP, SF, SSF: Branching Programs and Bottleneck Computation......Page 313
B.1 Reduction Definitions: :::;~, :::;~......Page 318
B.3 Facts about Reductions......Page 320
B.5 Bibliographic Notes......Page 321
References......Page 322
Index......Page 348