Abstract:

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.

We derive striking consequences for the complexities of these problems. For example, we show that certain fine-grained improvements on the runtime exponents of polynomial-time versions of Circuit-SAT would imply sub-exponential algorithms for Circuit-SAT on $2^{o(n)}$-size circuits, refuting the Exponential Time Hypothesis. We also show how slightly faster $\#$Circuit-SAT algorithms on large circuits can be used to prove uniform circuit lower bounds against deterministic linear-time computation. This result can be seen as providing an "algorithmic method" approach for proving uniform circuit lower bounds, which trades non-uniformity for a substantial reduction in the complexity of the hard function.