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.

Authors

• R. Ryan Williams

Keywords

• bootstrapping
• circuit lower bounds
• circuit satisfiability
• counting complexity
• fine-grained complexity
• quantified satisfiability