Self-Improvement for Circuit-Analysis Problems

Many results in fine-grained complexity reveal intriguing consequences from solving various SAT problems even slightly faster than exhaustive search. We prove a self-improving (or "bootstrapping") theorem for Circuit-SAT, #Circuit-SAT, and its fully-quantified version: solving one of these problems faster for "large" circuit sizes implies a significant speed-up for "smaller" circuit sizes. Our general arguments work for a variety of models solving circuit-analysis problems, including non-uniform circuits and randomized models of computation.

We derive striking consequences for the complexities of these problems, in both the fine-grained and parameterized setting. For example, we show that certain fine-grained improvements on the runtime exponents of polynomial-time versions of Circuit-SAT would imply subexponential-time algorithms for Circuit-SAT on 2 𝑜 (𝑛) -size circuits, refuting the Exponential Time Hypothesis. We also show that any algorithm for Circuit-SAT with 𝑘 inputs and 𝑛 gates running in 1000000 𝑘 + 𝑛 1+𝜀 time (for all 𝜀 > 0) would imply algorithms running in time (1 + 𝜀) 𝑘 + 𝑛 1+𝜀 time (for all 𝜀 > 0), also refuting the Exponential Time Hypothesis. Applying our ideas in the #Circuit-SAT setting, we prove new unconditional lower bounds against uniform circuits with symmetric gates for functions in deterministic linear time.