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, PP-uniform SIZE(nk). Namely, for any k, there is some language LP such that if size O(nk) circuits for L exist, they take super-polynomial time to generate.
- For every k, LOGSPACE does not have LOGSPACE-uniform branching programs of size nk.
- For every k, NP does not have PNP-uniform circuits of size nk.
- For every k, either P does not have non-uniform circuits of size nk, or QBF (the language of true quantified Boolean formulae) does not have P-uniform branching programs of size 2no(1).
2. Eliminating Non-Uniformity. We complement these results by proving a ``uniformization'' lemma for NC1, showing that any simulation of NC1 in ACC0poly or TC0poly 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 TC0: 'given a TC0 circuit C of nO(1) size which is promised to either be unsatisfiable or have at least 2n−1 satisfying assignments, determine which is the case.' We also use this lemma to prove that if NC1ACC0poly , then for all kc0 , the validity of quantified Boolean formulas (QBF) of size nk on n variables can be decided in deterministic time O(2nnc) .
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 kc0 , the validity of quantified Boolean CNFs of size nk with at most klogn alternations can be decided in time 2nnc , then NEXPNC1poly .
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−n12+ time deterministically (for some 0) then NEXPNC1poly . (Compare with the 3SAT problem, where 14n-time deterministic algorithms are known.) This extends the recent connections of Williams between SAT algorithms and circuit lower bounds, to QBF algorithms.
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, PP-uniform SIZE(nk). Namely, for any k, there is some language LP such that if size O(nk) circuits for L exist, they take super-polynomial time to generate.
- For every k, LOGSPACE does not have LOGSPACE-uniform branching programs of size nk.
- For every k, NP does not have PNP-uniform circuits of size nk.
- For every k, either P does not have non-uniform circuits of size nk, or QBF (the language of true quantified Boolean formulae) does not have P-uniform branching programs of size 2no(1).
2. Eliminating Non-Uniformity. We complement these results by proving a ``uniformization'' lemma for NC1, showing that any simulation of NC1 in ACC0poly or TC0poly 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 TC0: 'given a TC0 circuit C of nO(1) size which is promised to either be unsatisfiable or have at least 2n−1 satisfying assignments, determine which is the case.' We also use this lemma to prove that if NC1ACC0poly , then for all kc0 , the validity of quantified Boolean formulas (QBF) of size nk on n variables can be decided in deterministic time O(2nnc) .
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 kc0 , the validity of quantified Boolean CNFs of size nk with at most klogn alternations can be decided in time 2nnc , then NEXPNC1poly .
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−n12+ time deterministically (for some 0) then NEXPNC1poly . (Compare with the 3SAT problem, where 14n-time deterministic algorithms are known.) This extends the recent connections of Williams between SAT algorithms and circuit lower bounds, to QBF algorithms.
| Original language | English |
|---|---|
| Pages (from-to) | 59 |
| Number of pages | 15 |
| Journal | Electronic Colloquium on Computational Complexity (ECCC) |
| Volume | 19 |
| Publication status | Published - 2012 |