An Isomorphism Between Parameterized Complexity and Classical Complexity, for both Time and Space
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Shows a concrete mapping—called the miniaturization isomorphism—that turns a classical problem with size measure μ into a parameterized problem whose parameter is roughly ceil(μ(x)/log n), and proves it preserves reductions. Main claims: subexponential-time (2^{o(μ)}·poly(n)) for a classical problem iff its miniaturization is FPT, and k-Clique is FPT iff Clique runs in 2^{o(k log n)}·poly(n). Space analogue: parameterized logspace ⇔ algorithms using space f(k)+o(log n) and improvements of Savitch to o(log^2 n). Gives a database query lower bound conditioned on STCON not being in o(log^2 n).
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:44Exponential complexity
- 1:38Parameterized complexity
- 2:18The connection
- 3:29An equivalence
- 4:38Another equivalence
- 5:22A central problem in classical space complexity
- 8:46The space analogy (1)
- 11:10Easy direct proof for the space case
- 14:39Parameterization vs. Size Measure
- 16:33Tractability for time complexity
- 17:46Reductions
- 18:44Tractability for space complexity
- 20:27The Miniaturization
- 21:27The Isomorphism for Time Complexity (1)
- 25:38The Isomorphism for Space Complexity (3)
- 27:15An application
related talks
01h 07mComputational Complexity of Polynomial Time Problems: Introduction
01h 01mCircuit Complexity and Connections II
58mCircuit Complexity and Connections I
01h 05mParameterized Reductions
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
58mExponential-Time Algorithms
30mLocal Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descr
01h 21mComputational Complexity in Theory and in Practice