Preface......Page 6
Contents......Page 7
1 Introduction......Page 12
1.1 Context: Intractability and a New Way of Coping......Page 13
1.2 Structured Complexity Investigation......Page 14
1.2.1 Problem Statement......Page 15
1.3 Contributions......Page 16
1.3.1 Main Contributions......Page 19
1.4 Roadmap......Page 20
1.5.1 Black Box Algorithms for NP-complete Problems......Page 24
1.5.2 Focus on the Second Level of the Polynomial Hierarchy......Page 26
1.5.3 Complexity-Theoretic Assumptions......Page 27
1.5.4 Worst-Case Behavior of Fpt-Reductions......Page 28
Foundations......Page 30
2.1 Basics of Complexity Theory: P, NP......Page 31
2.1.1 Traditional Tractability: P......Page 32
2.1.2 Traditional Intractability: NP and NP-Completeness......Page 34
2.2.1 Polynomial Hierarchy......Page 36
2.2.2 Polynomial Space......Page 37
2.2.3 Alternating Turing Machines......Page 38
2.3 Bounded Query Complexity......Page 39
2.4 Non-uniform Complexity......Page 41
3.1 Fixed-Parameter Tractability......Page 43
3.1.1 Polynomial-Time Solvability for Constant Parameter Values......Page 44
3.1.2 Integers as Parameter Values......Page 45
3.2 Fixed-Parameter Intractability......Page 46
3.2.1 The Classes para-K......Page 47
3.2.2 The Weft Hierarchy......Page 48
3.2.3 The A-Hierarchy and First-Order Logic......Page 49
3.2.4 The Classes XNP, Xco-NP, XΞ£pi, and XΞ pi......Page 50
Beyond Para-NP......Page 52
4 Fpt-Reducibility to SAT......Page 53
4.1 Modern SAT Solvers......Page 55
4.1.1 The Success of SAT Solvers......Page 56
4.1.2 Algorithmic Techniques......Page 57
4.1.3 Successful Algorithms for Other NP-complete Problems......Page 58
4.2.1 Quantified Boolean Satisfiability......Page 60
4.2.2 Backdoors for Abductive Reasoning......Page 66
4.2.3 Backdoors for Disjunctive Answer Set Programming......Page 67
4.3 Sneak Preview: Fpt-Time Turing Reductions to SAT......Page 68
4.4.1 Hardness for para-Ξ£p2......Page 70
4.4.2 Hardness for A[2]......Page 71
5 The Need for a New Completeness Theory......Page 78
5.1 Running Example: Disjunctive Answer Set Programming......Page 79
5.1.1 Parameterized Variants Where Known Theory Suffices......Page 82
5.2 Motivating New Theory......Page 83
5.2.2 Membership in XNP and Xco-NP......Page 85
6 A New Completeness Theory......Page 91
6.1.1 The Hierarchies Ξ£2p [k, t] and Ξ£2p [k, t]......Page 92
6.1.2 Another Hierarchy......Page 94
6.2.1 Collapse......Page 95
6.2.2 Answer Set Programming and Completeness for Ξ£2p [k]......Page 96
6.2.3 Additional Characterizations of Ξ£2p [k]......Page 100
6.3 The Ξ£2p [k, t] Hierarchy......Page 121
6.3.1 A Normalization Result for Ξ£2p [k, 1]......Page 122
6.3.2 A Normalization Result for Ξ£2p [k, P]......Page 124
6.3.3 Answer Set Programming and Ξ£2p [k, P]-Completeness......Page 128
6.3.4 Alternating Turing Machine Characterization......Page 133
6.4.1 Relation of Ξ£2p [k] to Other Classes......Page 136
6.4.2 Relation of Ξ£2p [k, t] to Other Classes......Page 138
6.4.3 Relation Between Ξ£2p [k] and Ξ£2p [k, t]......Page 140
7 Fpt-Algorithms with Access to a SAT Oracle......Page 142
7.1 Known Parameterized Complexity Classes......Page 143
7.2 The Parameterized Complexity Class FPTNP[few]......Page 146
7.2.1 A Parameterized Variant of the Boolean Hierarchy......Page 147
7.2.2 Satisfiability Problems Complete for FPTNP[few]......Page 149
7.3 Lower Bounds on the Number of Oracle Queries......Page 151
7.4 Bounded Optimization Problems......Page 152
7.5 Witness-Producing SAT Oracles......Page 156
7.5.1 Comparing the Oracle Models for Decision Problems......Page 158
7.5.2 Comparing the Oracle Models for Search Problems......Page 160
Applying the Theory......Page 163
8 Problems in Knowledge Representation and Reasoning......Page 164
8.2 Abductive Reasoning......Page 165
8.3 Robust Constraint Satisfaction......Page 176
9 Model Checking for Temporal Logics......Page 183
9.1.1 Temporal Logics......Page 186
9.1.2 (Parameterized) Complexity Results......Page 188
9.2.1 PSPACE-hardness for Symbolic Model Checking......Page 189
9.2.2 An Fpt-Reduction to SAT for LTL\U,X......Page 193
9.3 Another Parameterized Variant of the Polynomial Hierarchy......Page 195
9.3.1 Alternative Characterizations......Page 196
9.4 Completeness for PH(level) and para-PSPACE......Page 198
10 Problems Related to Propositional Satisfiability......Page 207
10.1.1 Minimizing Implicants......Page 208
10.1.2 Minimizing DNF Formulas......Page 211
10.2 Inconsistency Repair......Page 216
11 Problems in Judgment Aggregation......Page 221
11.1 Judgment Aggregation......Page 223
11.1.1 Formula-Based Judgment Aggregation......Page 224
11.1.2 Constraint-Based Judgment Aggregation......Page 225
11.2.1 CNF Formulas......Page 227
11.2.2 Syntactic Restrictions......Page 229
11.2.3 Bounded Treewidth......Page 235
11.2.4 Small Counterexamples......Page 239
11.3 Computing Outcomes for the Kemeny Rule......Page 241
11.3.1 Upper Bounds for the Formula-Based Framework......Page 243
11.3.2 Lower Bounds for the Formula-Based Framework......Page 244
11.3.3 Upper Bounds for the Constraint-Based Framework......Page 249
11.3.4 Lower Bounds for the Constraint-Based Framework......Page 250
11.3.5 Overview......Page 252
12.1 SAS+ Planning......Page 253
12.2 Planning with Uncertainty......Page 254
12.3 Soft Goal Optimization......Page 259
13.1 Extending Graph Colorings......Page 262
13.2 Extending Cliques......Page 264
13.2.1 Ξ p2-Completeness for Clique-Extension......Page 268
Relation to Other Topics in Complexity Theory......Page 270
14 Subexponential-Time Reductions......Page 271
14.1 A Known Separation Result......Page 272
14.2 More Separation Results......Page 273
14.2.1 Separation Results for A[2]......Page 274
14.2.2 Separation Results for Ξ£2p[k] and Ξ£2p[k,t]......Page 278
14.3 Relating Ξ£2p[k] and Ξ£2p[k,t] to Each Other......Page 282
15 Non-uniform Parameterized Complexity......Page 284
15.1 Non-uniform Parameterized Complexity Classes......Page 285
15.1.2 Slice-Wise Advice......Page 286
15.1.3 Poly-size and Kernel-Size Advice......Page 287
15.2.1 Alternative Characterizations......Page 288
15.2.2 Separations......Page 292
15.3.1 Parameterized Knowledge Compilation......Page 300
15.3.2 (Conditional) Incompilability Results......Page 304
15.3.3 Restricting the Instance Space......Page 310
15.3.4 The Parameterized Compilability of Finding Small Cliques......Page 320
15.3.5 Other Parameterized Compilation Problems......Page 325
15.4 Parameterized Variants of the Karp-Lipton Theorem......Page 329
Conclusions......Page 332
16 Open Problems and Future Research Directions......Page 333
16.1 Improving Solving Methods......Page 334
16.2.1 Further Study of the Ξ£2p[*k,t] Hierarchy......Page 335
16.2.2 Further Study of the Relation Between Classes......Page 336
16.2.3 Other Topics......Page 337
16.3 Limited Non-determinism......Page 338
16.4 Witness Oracles......Page 340
16.5 Non-deterministic Kernelization......Page 341
17.1 Summary......Page 346
17.2 Research Impact......Page 349
A.1.1 Weighted Quantified Boolean Satisfiability......Page 351
A.1.2 Quantified Boolean Satisfiability......Page 354
A.1.3 Minimization for DNF Formulas......Page 355
A.1.4 Other......Page 356
A.2.1 Disjunctive Answer Set Programming......Page 358
A.2.2 Abductive Reasoning......Page 359
A.2.4 Planning......Page 360
A.3.2 Temporal Logics......Page 362
A.4.1 Agenda Safety in Judgment Aggregation......Page 363
A.4.2 Computing Outcomes in Judgment Aggregation......Page 365
A.5.1 Extending 3-Colorings......Page 368
A.5.2 Extending Cliques......Page 369
A.6 Alternating Turing Machines......Page 370
Appendix B Generalization to Higher Levels of the Polynomial Hierarchy......Page 371
B.1 The Parameterized Complexity Classes Ξ£pi[w,tPPtSATSATt]......Page 372
B.2 Inclusion Results......Page 374
B.3.1 The Case for i1 > i2......Page 378
B.3.2 The Case for i1 = i2......Page 379
B.3.3 The Case for i1 < i2......Page 380
References......Page 382
Index of Parameterized Problems......Page 392