Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR12-059 | 14th May 2012 08:57

#### Uniform Circuits, Lower Bounds, and QBF Algorithms

TR12-059
Authors: Rahul Santhanam, Ryan Williams
Publication: 14th May 2012 18:48
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint