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 ≥ 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 +ε ” in our results, for any ε > 0, would imply a breakthrough n ω(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+ε lower bound for MCSP [(log n ) c ] (for any ε > 0 and c ≥ 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: (a) For all α, ε > 0, there is a deterministic polynomial-time algorithm that finds satisfying assignments to every probabilistic formula of n 2−2α−ε size with at most 2 n α falsifying assignments. (b) If for some α, ε > 0, there is such an algorithm for probabilistic formulas of n 2−α+ε -size and 2 n α 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 ∈ [ poly ( n )] ⊆ {0,1} n × {0,1}, and every S ( n )-size formula F is inconsistent with the (partially defined) function f . We prove that for all ε > 0, there is an explicit obstruction against n 2−ε -size formulas, and prove that there is an explicit obstruction against n 2+ε -size formulas for some ε > 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.

Authors

• Lijie Chen 0001
• Ce Jin 0001
• R. Ryan Williams

Keywords

• de morgan formulas
• hardness magnification
• quantified derandomization