The Complexity Theory Companion

Description

Preface......Page 7 Contents......Page 11 1. The Self-Reducibility Technique......Page 15 1.1 GEM There Are No Sparse NP-Complete Sets Unless P=NP......Page 16 1.2 The 'I'uring Case......Page 32 1.3 The Case of Merely Putting Sparse Sets in NP - P The Hartmanis-lmmerman-Sewelson Encoding......Page 36 1.5 Bibliographic Notes......Page 40 2. The One-Way Function Technique......Page 45 2.1 GEM Characterizing the Existence of One-Way Functions......Page 46 2.2 Unambiguous One-Way Functions Exist If and Only If Bounded-Ambiguity One-Way Functions Exist......Page 49 2.3 Strong, Total, Commutative, Associative One-Way Functions Exist If and Only If One-Way Functions Exist......Page 50 2.4 OPEN ISSUE Low-Ambiguity, Commutative, Associative One-Way Functions......Page 56 2.5 Bibliographic Notes......Page 57 3.1 GEM The Semi-feasible Sets Have Small Circuits......Page 59 3.2 Optimal Advice for the Semi-feasible Sets......Page 62 3.3 Unique Solutions Collapse the Polynomial Hierarchy......Page 70 3.5 Bibliographic Notes......Page 77 4. The Isolation Technique......Page 81 4.1 GEM Isolating a Unique Solution......Page 82 4.2 Toda's Theorem PH ~ pPP......Page 86 4.3 NLpoly = ULpoly......Page 96 4.5 Bibliographic Notes......Page 101 5.1 Framing the Question: Is #P Closed Under Proper Subtraction......Page 105 5.2 GEM: A Complexity Theory for Feasible Closure Properties of #P......Page 107 5.3 Intermediate Potential Closure Properties......Page 113 5.4 A Complexity Theory for Feasible Closure Properties of OptP......Page 117 5.5 OPEN ISSUE: Characterizing Closure Under Proper Decrement......Page 119 5.6 Bibliographic Notes......Page 120 6. The Polynomial Interpolation Technique......Page 123 6.1 GEM: Interactive Protocols for the Permanent......Page 124 6.2 Enumerators for the Permanent......Page 133 6.3 IP = PSPACE......Page 136 6.4 MIP = NEXP......Page 147 6.6 Bibliographic Notes......Page 177 7. The Nonsolvable Group Technique......Page 181 7.1 GEM: Width-5 Branching Programs Capture Nonuniform-NC1......Page 182 7.2 Width-5 Bottleneck Machines Capture PSPACE......Page 190 7.3 Width-2 Bottleneck Computation......Page 195 7.5 Bibliographic Notes......Page 206 8.1 GEM: The Random Restriction Technique and a Polynomial-Size Lower Bound for Parity......Page 211 8.2 An Exponential-Size Lower Bound for Parity......Page 221 8.3 PH and PSPACE Differ with Probability One......Page 232 8.4 Oracles That Make the Polynomial Hierarchy Infinite......Page 236 8.6 Bibliographic Notes......Page 245 9. The Polynomial Technique......Page 249 9.1 GEM: The Polynomial Technique......Page 250 9.2 Closure Properties of PP......Page 255 9.3 The Probabilistic Logspace Hierarchy Collapses......Page 266 9.4 OPEN ISSUE: Is PP Closed Under Polynomial-Time Turing Reductions......Page 273 9.5 Bibliographic Notes......Page 274 A. A Rogues' Gallery of Complexity Classes......Page 277 A.1 P: Determinism......Page 278 A.2 NP: Nondeterminism......Page 280 A.3 Oracles and Relativized Worlds......Page 282 A.4 The Polynomial Hierarchy and Polynomial Space: The Power of Quantifiers......Page 284 A.5 E, NE, EXP, and NEXP ................................ 27......Page 18 A.6 P /Poly: Small Circuits......Page 290 A.7 L, NL, etc.: Logspace Classes......Page 291 A.8 NC, AC, LOGCFL: Circuit Classes......Page 293 A.9 UP, FewP, and US: Ambiguity-Bounded Computation and Unique Computation......Page 295 A.10 #P: Counting Solutions......Page 300 A.ll ZPP, RP, coRP, and BPP: Error-Bounded Probabilism......Page 302 A.12 PP, C=P, and SPP: Counting Classes......Page 304 A.13 FP, NPSV, and NPMV: Deterministic and Nondeterministic Functions......Page 305 A.14 P-Sel: Semi-feasible Computation......Page 308 A.16 SpanP, OptP: Output-Cardinality and Optimization Function Classes......Page 311 A.17 IP and MIP: Interactive Proof Classes......Page 313 A.18 PBP, SF, SSF: Branching Programs and Bottleneck Computation......Page 314 B.1 Reduction Definitions: :::;~, :::;~......Page 319 B.3 Facts about Reductions......Page 321 B.5 Bibliographic Notes......Page 322 References......Page 323 Index......Page 349