Exploring Circuit Lower Bounds and NP Complexity Theory

Circuit Lower Bounds A combinatorial approach to P vs NP Shachar Lovett

Computation Input Program Code Memory Program code is constant Input has variable length (n) Run time, memory grow with input length Efficient algorithms = run time, memory poly(n)

P vs NP P = problems we can solve = efficient algorithm to find solution NP = problems we want to solve = efficient algorithm to verify solution Examples: graph 3-coloring, satisfiability ,

Challenge How can you prove that some computational problems require >> polynomial time? In particular, one in NP Combinatorial approach: circuits Replace uniform computation by a more combinatorial object

Circuits Complex computation = iteration of many small simple computations Majority(X,Y,Z) OR AND AND AND x Y Z

Circuits Complex computation = iteration of many small simple computations Simple = any complete basis (e.g. AND,OR,NOT) f(X1, ,Xn) x1x2x3x4x5x6x7x8 xn

Algorithms vs circuits f(X1, ,Xn) Input Code Memory x1 x2 x3 x4 x5 x6 x7 x8 xn Circuits are as powerful* as algorithms: Problems with efficient (poly-time) algorithms also have poly-size circuits Revised challenge: show poly-size circuits cannot solve all interesting computational problems

Lower bounds Goal: show poly-size circuits cannot solve NP Can prove lower bounds for restricted circuit models Monotone circuits Bounded depth circuits General technique: 1. Approximate circuit by a nice mathematical model 2. Show the mathematical model cannot solve the problem (not even approximately)

Monotone circuits Monotone circuits: circuits with just AND-OR gates (no NOT gates) Compute monotone functions (e.g clique) Can clique have poly-size monotone circuits? [Razborov 85, Alon-Boppana 87]: No. Clique requires exponential size monotone circuits

Monotone circuits Input: n edges of graph G on m n1/2 vertices Output: does G have large clique? Circuit: poly-size with AND-OR gates Step 1: approximate AND-OR circuit by lattice Step 2: show lattice cannot approximate clique f(X1, ,Xn) x1x2x3x4x5x6x7x8 x n

Bounded depth circuits Small depth = parallel computation Efficient algorithms = poly(n) depth Can prove lower bounds for depth << log(n) f(X1, ,Xn) depth x1x2x3x4x5x6x7x8 xn

Lower bounds for AND-OR-NOT circuits Parity(x1, ,xn) = sum of bits modulo 2 Computed by small AND-OR-NOT circuits of depth log(n) Can the depth be reduced, while maintaining small size? [Ajtai 83, Furst-Saxe-Sipser 84]: No. small (sub- exponential) AND-OR-NOT circuits of depth <<log(n) cannot compute parity [Yao 85, Hastad 86]: not even approximately

Lower bounds for AND-OR-NOT circuits Main idea: random restrictions of input set most inputs bits to random 0,1 values; leave remaining variables alive AND Simple computations: AND, OR, NOT X1 Xn Gates with many inputs are fixed by random restriction Iterate to make entire circuit simple (decision tree) Parity doesn t simplify (becomes parity of fewer inputs)

Lower bounds for AND-OR-NOT- PARITY circuits What if we also allow parity gates as simple computations? MOD3(x1, ,xn) = sum of bits modulo 3 Intuition: parities shouldn t help compute MOD3 [Razborov 87, Smolensky 87]: small (sub- exponential) AND-OR-NOT-PARITY circuits of depth <<log(n) cannot compute MOD3

Lower bounds for AND-OR-NOT- PARITY circuits Local computation: AND, OR, NOT, PARITY Random restrictions fail: don t simplify parity Can approximate local computations by low- degree polynomials modulo 2 (and by composition, approximate the entire circuit) Low degree polynomials modulo 2 cannot compute MOD3

Lower bounds for AND-OR-NOT- PARITY-MOD3 circuits What if we allow both PARITY and MOD3 gates as simple computation? Conjecture: cannot compute MOD5 in small size and depth <<log(n) [Williams 10]: cannot compute all NEXP - exponential analog of NP (problems whose solution can be verified in exponential time)