Here is an accessible, algorithmically oriented guide to some of the most interesting techniques of complexity theory. The book shows that simple algorithms are at the heart of complexity theory. The book is organized by technique rather than by topic. Each chapter focuses on one technique: what it is, and what results and applications it yields.
Author(s): Lane A. Hemaspaandra, Mitsunori Ogihara
Series: Texts in Theoretical Computer Science. An EATCS Series
Publisher: Springer
Year: 2001
Language: English
Pages: 383
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 16
1.2 The Turing 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 44
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. The Tournament Divide and Conquer Technique......Page 58
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 80
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 0
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
