Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-065 | 2nd May 2020 05:45

Sharp Threshold Results for Computational Complexity



We establish several ``sharp threshold'' results for computational complexity. For certain tasks, we can prove a resource lower bound of $n^c$ for $c \geq 1$ (or obtain an efficient circuit-analysis algorithm for $n^c$ size), there is strong intuition that a similar result can be proved for larger functions of $n$, yet we can also prove that replacing ``$n^c$'' with ``$n^{c+\varepsilon}$'' in our results, for any $\varepsilon > 0$, would imply a breakthrough $n^{\omega(1)}$ lower bound.

We first establish such a result for Hardness Magnification. We prove (among other results) that for some $c$, the Minimum Circuit Size Problem for $(\log n)^c$-size circuits on length-$n$ truth tables (${MCSP}[(\log n)^c]$) does not have $n^{2-o(1)}$-size probabilistic formulas. We also prove that an $n^{2+\varepsilon}$ lower bound for ${MCSP}[(\log n)^c]$ (for any $\varepsilon > 0$ and $c \geq 1$) would imply major lower bound results, such as ${NP}$ does not have $n^k$-size formulas for all $k$, and $\#{SAT}$ does not have log-depth circuits.
Similar results hold for time-bounded Kolmogorov complexity. Note that cubic size lower bounds are known for probabilistic De Morgan formulas (for other functions).

Next we show a sharp threshold for Quantified Derandomization (QD) of probabilistic formulas.
(1) For all $\alpha, \varepsilon > 0$, there is a deterministic polynomial-time algorithm that finds satisfying assignments to every probabilistic formula of $n^{2-2\alpha-\varepsilon}$ size with at most $2^{n^{\alpha}}$ falsifying assignments.
(2) If for some $\alpha, \varepsilon > 0$, there is such an algorithm for probabilistic formulas of $n^{2-\alpha+\varepsilon}$-size and $2^{n^{\alpha}}$ unsatisfying assignments, then a full derandomization of ${NC}^1$ follows: a deterministic poly-time algorithm additively approximating the acceptance probability of any polynomial-size formula. Consequently, ${NP}$ does not have $n^k$-size formulas, for all $k$.

Finally we show a sharp threshold result for Explicit Obstructions, inspired by Mulmuley's notion of explicit obstructions from GCT. An explicit obstruction against $S(n)$-size formulas is a poly-time algorithm $A$ such that $A(1^n)$ outputs a list $\{(x_i,f(x_i))\}_{i \in [\mathrm{poly}(n)]} \subseteq \{0,1\}^n \times \{0,1\}$, and every $S(n)$-size formula $F$ is inconsistent with the (partially defined) function $f$. We prove that for all $\varepsilon > 0$, there is an explicit obstruction against $n^{2-\varepsilon}$-size formulas, and prove that there is an explicit obstruction against $n^{2+\varepsilon}$-size formulas for some $\varepsilon > 0$ if and only if there is an explicit obstruction against all polynomial-size formulas. This in turn is equivalent to the statement that ${E}$ does not have $2^{o(n)}$-size formulas, a breakthrough in circuit complexity.

ISSN 1433-8092 | Imprint