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:
1. 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 \not \subseteq P-uniform SIZE(n^k). Namely, for any k, there is some language L \in P such that if size O(n^k) 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^k.
- For every k, NP does not have P^{NP}_{||}-uniform circuits of size n^k.
- For every k, either P does not have non-uniform circuits of size n^{k}, or QBF (the language of true quantified Boolean formulae) does not have P-uniform branching programs of size 2^{n^{o(1)}}.
2. Eliminating Non-Uniformity. We complement these results by proving a ``uniformization'' lemma for NC^1, showing that any simulation of NC^1 in ACC^0/poly or TC^0/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 2^{n-\omega(\log n)}-time algorithm for the following promise problem suffices for proving NEXP lower bounds against TC^0: 'given a TC^0 circuit C of n^{O(1)} size which is promised to either be unsatisfiable or have at least 2^{n-1} satisfying assignments, determine which is the case.' We also use this lemma to prove that if NC^1 \subset ACC^0/poly, then for all k,c > 0, the validity of quantified Boolean formulas (QBF) of size n^k on n variables can be decided in deterministic time O(2^n/n^c).
3. 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^{k} with at most k \log n alternations can be decided in time 2^n/n^c, then NEXP \not\subset NC^1/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 2^{n-n^{1/2+\epsilon}} time deterministically (for some \epsilon > 0) then NEXP \not\subset NC^1/poly. (Compare with the 3SAT problem, where 1.4^n-time deterministic algorithms are known.) This extends the recent connections of Williams between SAT algorithms and circuit lower bounds, to QBF algorithms.
