Understanding MCSP and SAT in Circuit Complexity

Reading MCSP through SAT Rahul Santhanam University of Oxford

Structure of the Talk Introduction to MCSP Comparing MCSP and SAT Is MCSP NP-complete? Is MCSP in polynomial time? MCSP and Circuit Lower Bounds

Structure of the Talk Introduction to MCSP Comparing MCSP and SAT Is MCSP NP-complete? Is MCSP in polynomial time? MCSP and Circuit Lower Bounds

Boolean Circuits Important model in theory and practice Basic facts about circuit complexity Every Boolean function F on n bits has circuits of size 2n Most Boolean functions require circuits of size (2n/n), by a straightforward counting argument Can we come up with an explicit function that is hard? Main Problem of circuit complexity: Show that there is a function in exponential time (and preferably in NP) which cannot be computed by polynomial-size Boolean circuits

The Minimum Circuit Size Problem (MCSP) Input: A Boolean function F on n bits, given by its truth table of size N=2n. Also a parameter s <= N Output: Yes iff F has a Boolean circuit of size at most s We also consider MCSP[s] where s is a fixed function of N. Our default choice will be s=N0.1

MCSP and SAT SAT (and its variants such as #SAT): We are given a circuit and asked questions about the truth table of the function computed by the circuit, eg., does the truth table have a 1? How many 1 s are there in the truth table? MCSP: Inverse problem to SAT. We are given a truth table and asked whether there are small circuits for it Note that both SAT and MCSP are meta-computational problems they are computational problems that are about computation

MCSP and SAT We know a lot about SAT SAT is NP-complete, and this has been used to show many other problems are NP-complete. In practice, NP-hard problems are often solved by encoding them as SAT instances and using a SAT solver Probabilistically checkable proofs (PCPs) for SAT are the basis for the theory of approximation for NP-hard problems Williams recent approach to circuit lower bounds is via non-trivial algorithms for SAT On the other hand, MCSP remains quite mysterious

The Complexity of MCSP MCSP is in NP Given the truth table Y (of size N) of a Boolean function, and a parameter s, guess a circuit C of size at most s and check for each i, 1 <= i <= N that C(i) = Yi This takes time at most N poly(s), which is poly(N) since s <= N Is MCSP in P? Unclear how to solve MCSP without doing a brute force search over small circuits If not, then perhaps MCSP is NP-complete? We don t know! MCSP is the prime example of a natural problem whose complexity status is unclear

History of MCSP MCSP has been studied since the 1950s by theorists in the Soviet Union, long before there was any work in complexity theory in North America [Trakhtenbrot] Leonid Levin delayed publishing his results on NP-completeness because he hoped to clarify the complexity of MCSP Recent interest in the problem following work of [Kabanets-Cai], which builds on [Razborov-Rudich]

Why is MCSP Important? It is a basic problem about circuit complexity of functions The example of SAT shows us that understanding the complexity of meta-computational problems pays rich dividends Connections to learning, cryptography, proof complexity etc. More broadly, MCSP is a natural problem about compressing strings

Structure of the Talk Introduction to MCSP Comparing MCSP and SAT Is MCSP NP-complete? Is MCSP in polynomial time? MCSP and Circuit Lower Bounds

Explicit Constructions Let L be a problem The explicit construction problem for L Given n in unary, compute a string Xnin L, |Xn|=n For most natural problems L in NP, the explicit construction problem for L or Lccan be efficiently solved Eg., in the case of SAT, it is easy to compute a satisfiable or unsatisfiable formula of any given length

Explicit Constructions for MCSP? Let L be a problem The explicit construction problem for L Given n in unary, compute a string Xnin L, |Xn|=n For natural problems L in NP, the explicit construction problem for L or Lc can be efficiently solved Eg., in the case of SAT, it is easy to compute a satisfiable or unsatisfiable formula of any given length However, for MCSP[N0.1]c, unclear how to solve the explicit construction problem efficiently Solving this problem efficiently would give us an explicit function without circuits of sub-exponential size, which is the Main Problem of circuit complexity

Paddability A problem L is paddable if there is a poly-time computable f such that for any string x and integer n, |f(x,1n)| = n, and f(x,1n) in L iff x in L SAT and other natural NP-complete problems are paddable Note that for any non-trivial problem L, paddability implies explicit constructions for L and Lc We don t know if MCSP[N0.1] is paddable a positive answer would again solve the Main Problem of circuit complexity

Reducing Search to Decision Let L be a problem in NP The decision problem for L is to decide, given x, whether x in L The search problem for L is to find, given x in L, a proof or witness that x in L Classical result: SAT is decidable in polynomial time iff the search problem for SAT is solvable in polynomial time

Search to Decision for MCSP? The idea of the search-to-decision reduction for SAT doesn t seem to work for MCSP Unclear how to find a circuit for a given truth table bit by bit just by asking questions about MCSP Until recently, nothing was known about whether search reduces to decision for MCSP Recent paper of [Carmosino-Impagliazzo-Kabanets-Kolokolova] gives approximate search-to-decision reduction if a poly-time decision procedure exists, so does a poly-time search procedure giving an approximating circuit

Learning Theory: A Digression Approximate search-to-decision reduction for MCSP is closely related to the problem of learning Boolean circuits [CIKK] establish their approximate search-to-decision reduction by proving a result about learning

Learning and MCSP Learning model: The learner is given oracle access to a target function and outputs a good hypothesis (i.e., small circuit) for the target function if such a hypothesis exists Search version of MCSP: Given a truth table, output a small circuit for the truth table if one exists Intuitively, if there is an efficient learner, one can solve (approximately) the search version of MCSP, simply using the input truth table to answer oracle queries [CIKK] show that an efficient decision procedure for MCSP yields an efficient learner

Structure of the Talk Introduction to MCSP Comparing MCSP and SAT Is MCSP NP-complete? Is MCSP in polynomial time? MCSP and Circuit Lower Bounds

Natural Problems and NP-Completeness For almost all natural problems in NP, we know either that they are in P (Linear Programming, Bipartite Matching, Primality etc.) or that they are NP-complete (SAT, Clique, Integer Linear Programming, Knapsack etc.) There are some exceptions, eg., Factoring and Graph Isomorphism, but for these problems, we have complexity-theoretic evidence against NP-completeness MCSP is a rare problem for which there is no clear evidence either in favour of or against NP-completeness

The Difficulty of Proving NP-Completeness for MCSP Despite major efforts, we are very far from proving MCSP is NP- complete Of course, one possible reason is that MCSP is not NP-complete But are there obvious obstacles we can identify to showing NP- completeness?

The Explicit Construction Obstacle Suppose we try to show MCSP is NP-hard using a normal reduction from SAT What is a normal reduction? Poly-time Output length and parameter depend only on the input length Result [Kabanets-Cai]: A normal reduction from SAT to MCSP would solve the Main Problem of circuit complexity

Proof Sketch by Picture f SAT MCSP f SATc MCSPc Assume there is a normal reduction f mapping SAT to MCSP

Proof Sketch by Picture f SAT MCSP f SATc MCSPc 1n n f( n) Compose f with explicit construction of unsat formula n to get explicit hard function

The Explicit Construction Obstacle Several results since [Kabanets-Cai] paper giving evidence of the difficulty of proving NP-completeness of MCSP But none of these results say anything about the likelihood of MCSP being NP-complete It s possible that if we knew how to prove circuit lower bounds, we would also know how to show MCSP is NP-complete. Understanding the complexity of MCSP seems to require understanding circuit complexity better

NP-Completeness: A Different Perspective We have defined MCSP for Boolean circuits, but the analogous problem can be defined and studied for any class of circuits, eg., DNFs, AC0 (constant-depth circuits), Formulas etc. What can we say about NP-completeness or otherwise of C-MCSP for other classes of circuits C?

DNF-MCSP It has been known since 1979 that DNF-MCSP is NP-complete! [Masek] Intuitively, making the class of circuits more general should only make the problem harder However, the explicit construction obstacle makes this intuition hard to implement But perhaps we could aim to make incremental progress to NP- completeness of general MCSP, by considering larger and larger classes of circuits? This is similar in spirit to the approach taken to circuit lower bounds

A New NP-Completeness Result Recent result [Hirahara-Oliveira-S]: C-MCSP is NP-complete for C = DNFs of Parities Open problem: Show some sort of hardness result for C = AC0 or even C = circuits of depth 3

Structure of the Talk Introduction to MCSP Comparing MCSP and SAT Is MCSP NP-complete? Is MCSP in polynomial time? MCSP and Circuit Lower Bounds

The Unlikelihood of MCSP in P Intuitively, we shouldn t be able to solve MCSP better than doing brute-force search over small circuits But is there a way to justify this intuition? One way would be to prove MCSP NP-complete, but that seems difficult Perhaps there are other ways of giving complexity-theoretic evidence against MCSP in P? Connections with proof complexity and cryptography

Natural Proofs [Razborov-Rudich] defined and studied natural proofs as a way to formalize known approaches to proving circuit lower bounds They showed that natural proofs cannot prove superpolynomial size circuit lower bounds under a standard crypto assumption, i.e., that one-way functions exist Their result implies MCSP is not in P if one-way functions exist

MCSP and Pseudorandomness [GGM] showed that if one-way functions exist, then there are pseudorandom functions functions computed by small circuits, but such that no efficient procedure can distinguish between pseudorandom functions and random ones With high probability, a random function has very large circuit complexity, while pseudorandom functions all have small circuit complexity, so if MCSP is decidable by a polynomial-time procedure A, A would distinguish between random functions and pseudorandom ones This argument in fact shows that MCSP is hard on average if one-way functions exist

Structure of the Talk Introduction to MCSP Comparing MCSP and SAT Is MCSP NP-complete? Is MCSP in polynomial time? MCSP and Circuit Lower Bounds

Circuit Lower Bounds for MCSP? Though there are no general circuit lower bounds for explicit functions, there are lower bounds for weaker classes Can we show such lower bounds for MCSP, thus getting some unconditional indication of hardness? [Allender] showed that MCSP does not have polynomial-size constant depth circuits In recent work, [Hirahara-S] show that MCSP does not have Boolean formulas of size N2- for any > 0

Circuit Lower Bounds for MCSP? Can we say anything at all about general circuit lower bounds for MCSP? Consider Gap-MCSP[s, s ], which is a promise problem where the YES instances are truth tables with circuit complexity at most s and the NO instances are truth tables with circuit complexity at least s Recent work [Oliveira-Pich-S]: Circuit lower bound of N1+ on Gap- MCSP[f(N)/log2(N), f(N)] for any > 0 and f(N) = No(1) would imply NP P!