Weak lower bounds on resource-bounded compression imply strong separations of complexity classes

The Minimum Circuit Size Problem (MCSP) asks to determine the minimum size of a circuit computing a given truth table. MCSP is a natural and powerful string compression problem using bounded-size circuits. Recently, Oliveira and Santhanam [FOCS 2018] and Oliveira, Pich, and Santhanam [ECCC 2018] demonstrated a “hardness magnification” phenomenon for MCSP in restricted settings. Letting MCSP[ s ( n )] be the problem of deciding if a truth table of length 2 n has circuit complexity at most s ( n ), they proved that small (fixed-polynomial) average case circuit/formula lower bounds for MCSP[2 √ n ], or lower bounds for approximating MCSP[2 o ( n ) ], would imply major separations such as NP ⊄ BPP and NP ⊄ P / poly . We strengthen their results in several directions, obtaining magnification results from worst-case lower bounds on exactly computing the search version of generalizations of MCSP[ s ( n )], which also extend to time-bounded Kolmogorov complexity. In particular, we show that search-MCSP[ s ( n )] (where we must output a s ( n )-size circuit when it exists) admits extremely efficient AC 0 circuits and streaming algorithms using Σ 3 SAT oracle gates of small fan-in (related to the size s ( n ) we want to test). For A : {0,1} ⋆ → {0,1}, let search-oracleMCSP A [ s ( n )] be the problem: Given a truth table T of size N =2 n , output a Boolean circuit for T of size at most s ( n ) with AND, OR, NOT, and A -oracle gates (or report that no such circuit exists). Some consequences of our results are: (1) For reasonable s ( n ) ≥ n and A ∈ PH , if search-MCSP A [ s ( n )] does not have a 1-pass deterministic poly( s ( n ))-space streaming algorithm with poly( s ( n )) update time, then P ≠ NP . For example, proving that it is impossible to synthesize SAT-oracle circuits of size 2 n /log ⋆ n with a streaming algorithm on truth tables of length N =2 n using N ε update time and N ε space on length- N inputs (for some ε > 0) would already separate P and NP . Note that some extremely simple functions, such as EQUALITY of two strings, already satisfy such lower bounds. (2) If search-MCSP[ n c ] lacks Õ( N )-size, Õ(1)-depth circuits for a c ≥ 1, then NP ⊄ P / poly . (3) If search-MCSP[ s ( n )] does not have N · poly( s ( n ))-size, O (log N )-depth circuits, then NP ⊄ NC 1 . Note it is known that MCSP[2 √ n ] does not have formulas of N 1.99 size [Hirahara and Santhanam, CCC 2017]. (4) If there is an ε > 0 such that for all c ≥ 1, search-MCSP[2 n / c ] does not have N 1+ε -size O (1/ε)-depth ACC 0 circuits, then NP ⊄ ACC 0 . Thus the amplification results of Allender and Koucký [JACM 2010] can extend to problems in NP and beyond. Furthermore, if we substitute ⊕ P , PP , PSPACE , or EXP -complete problems for the oracle A , we obtain separations for those corresponding complexity classes instead of NP . Analogues of the above results hold for time-bounded Kolmogorov complexity as well.

Authors

• Dylan M. McKay
• Cody D. Murray
• R. Ryan Williams

Keywords

• Kolmogorov complexity
• hardness magnification
• minimum circuit size problem
• streaming algorithms