Uniform Circuits, Lower Bounds, and QBF Algorithms
Rahul Santhanam, Ryan Williams · Electronic colloquium on computational complexity · 2012
We explore the relationships between circuit complexity, the complexity of generating circuits, and circuit-analysis algorithms. Our results can be roughly divided into three parts: • Lower Bounds Against Medium-Uniform Circuits. Informally, a circuit class is “medium uniform” if it can be generated by an algorithmic process that is somewhat complex but not infeasible. We prove several unconditional lower bounds against medium uniform circuit classes, including – For every k, P 6⊆ P-uniformSIZE(n). Namely, for any k, there is some language L ∈ P such that if size O(n) circuits for L exist, they take super-polynomial time to generate. – For every k, LOGSPACE does not have LOGSPACE-uniform branching programs of size n. – For every k, NP does not have P || -uniform circuits of size n . – For every k, either P does not have non-uniform circuits of size n, or QBF (the language of true quantified Boolean formulae) does not have P-uniform branching programs of size 2 o(1) . These lower bounds apply an indirect diagonalization argument which simulates a “medium uniform” class with a low-uniform class using small amount of non-uniformity. • Eliminating Non-Uniformity. We complement these results by proving a “uniformization” lemma for NC, showing that any simulation of NC in ACC/poly or TC/poly can be transformed into a uniform simulation using small advice. This lemma can be used to simplify part of the proof that faster SAT algorithms imply NEXP circuit lower bounds, and show that a nondeterministic 2n−ω(logn)-time algorithm for the following promise problem suffices for proving NEXP lower bounds against TC: given a TC circuit C of n size which is promised to be either unsatisfiable or have at least 2n−1 satisfying assignments, determine which is the case. We also use this lemma to prove that if NC ⊂ ACC/poly, then for all constants k, c > 0, the validity of quantified Boolean formulas (QBF) of size n on n variables can be decided in deterministic time O(2/n). • The complexity of QBF. Finally, we study the time complexity of QBF itself, and its application to lower bounds. As a partial converse to the above results, we show that if for each k, c > 0, the validity of quantified Boolean CNFs of size n with at most k log n alternations can be decided in time 2/n, then NEXP 6⊂ NC/poly. We also show that the exponential time complexities of quantified k-CNF and quantified (unrestricted) formulas are essentially identical. As a consequence, if quantified 3CNF formulas of n variables and poly(n) size can be decided in 2n−n 1/2+e time deterministically (for some e > 0) then NEXP 6⊂ NC/poly. (Compare with the 3SAT problem, where 1.4-time deterministic algorithms are known.) This extends the recent connections of Williams between SAT algorithms and circuit lower bounds, to QBF algorithms. ISSN 1433-8092 Electronic Colloquium on Computational Complexity, Report No. 59 (2012)