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.
