Circuit Satisfiability in Complexity Theory

CMSC 28100 Introduction to Complexity Theory Complexity Theory Spring 2024 Instructor: William Hoza 1

Circuit satisfiability We say that a circuit ? is satisfiable if there exists ? {0,1}? such that ? ? = 1 Let CIRCUIT-SAT = { ? ? is a satisfiable circuit} Theorem: CIRCUIT-SAT is NP-complete. 2

Proof that CIRCUIT-SAT NP Given ? , where ? is an ?-input 1-output circuit: Pick ? 0,1? at random 1. Check whether ? ? = 1 (recall CIRCUIT-VALUE P) 2. Accept if ? ? = 1; reject if ? ? = 0 3. 3

Proof that CIRCUIT-SAT is NP-hard Let ? be any language in NP Our job: Design a mapping reduction from ? to CIRCUIT-SAT Idea: Let s build a verification circuit for ? 4

Given ?, how do we efficiently construct ?? Proof that CIRCUIT-SAT is NP-hard A: Simulate ? on ? and output the corresponding circuit B: Calculate ?, then make a ? ? grid of copies of ?0 (a fixed circuit) C: Inspect the transition function of ? and implement it as a circuit D:We don t; all that matters is the fact that ? exists Let ? be a nondeterministic TM that decides ? in time ? ? = poly ? Respond at PollEv.com/whoza or text whoza to 22333 Let ? = ?#? ? accepts ? when initialized with ? on tape 2 ? P PSIZE, and as discussed last time, the circuits are efficiently constructible Reduction step 1: Given ?, construct ? , where ? is a circuit that computes ?? for ? = ? + 1 + ? ? 5

Proof that CIRCUIT-SAT is NP-hard Reduction step 2 ? ? ?2 ?3 ?4 ?5 ?6 ?7 ?? 1 1 0 1 ?1 ?2 ?? ?1 0 ?# hard-coded into circuit ? ? if and only if there exists ? such that ? ?#? = 1 Reduction: ? ? = ? , where ? ? = ? ?#? 6

Proof that CIRCUIT-SAT is NP-hard Reduction: ? ? = ? , where ? ? = ? ?#? and ? computes ?? YES maps to YES: If ? ?, then Pr ? accepts ? 0 Therefore, there exists ? 0,1? ? such that ?#? ? Therefore, ? ?#? = 1 Therefore, ? ? = 1, so ? is satisfiable 7

Proof that CIRCUIT-SAT is NP-hard Reduction: ? ? = ? , where ? ? = ? ?#? and ? computes ?? NO maps to NO: Suppose ? is satisfiable, i.e., there exists ? 0,1? ? such that ? ? = 1 Then ? ?#? = 1, so ?#? ? Therefore, Pr ? accepts ? 0 Therefore, ? ? 8

Proof that CIRCUIT-SAT is NP-hard Reduction: ? ? = ? , where ? ? = ? ?#? and ? computes ?? Polynomial-time computable: 1. Compute ? . This takes poly ? = poly ? time 2. Plug in ?#. This takes poly ? time 9

NP-completeness NP-hard CIRCUIT-SAT NP-complete NP P 10

What else is NP-complete? We showed that CIRCUIT-SAT is NP-complete It turns out that a huge number of natural, interesting, and important languages are NP-complete! For example, we still want to show that CLIQUE is NP-complete To prove NP-hardness, we can chain reductions together 11

Chaining reductions together Claim: Suppose ?HARDis NP-hard and there is a polynomial-time mapping reduction ? from ?HARD to ?NEW. Then ?NEW is NP-hard Proof: Let ? be any language in NP There is a polynomial-time mapping reduction ? from ? to ?HARD Reduction from ? to ?NEW: ? = ? ? ? Poly-time computable YES maps to YES NO maps to NO 12

Chaining reductions together Consequence: To prove that CLIQUE is NP-complete, there is no need to reduce from an arbitrary language in NP We merely need to do a reduction from the one language CIRCUIT-SAT That s nice, but it s still not clear how to reduce CIRCUIT-SAT to CLIQUE Plan: We will reduce CIRCUIT-SAT to 3-SAT and 3-SAT to CLIQUE 13

?-CNF formulas Recall: A CNF formula is an AND of ORs of literals Definition: A ?-CNF formula is a CNF formula in which every clause has at most ? literals Example of a 3-CNF formula with two clauses: ? = ?1 ?2 ?6 ?5 ?1 ?2 14

The Cook-Levin Theorem Define ?-SAT = { ? ? is a satisfiable ?-CNF formula} The Cook-Levin Theorem: 3-SAT is NP-complete Proof: We need to show two things. 1. We need to show 3-SAT NP. What is the certificate? 2. We need to show that 3-SAT is NP-hard. Reduction from CIRCUIT-SAT 15

Gate gadgets Define the following Boolean functions: CHECK-NOT ?,? = 1 if ? = ? 0 otherwise CHECK-AND ?,?,? = 1 if ? = ? ? 0 otherwise CHECK-OR ?,?,? = 1 if ? = ? ? 0 otherwise Each can be represented by a 3-CNF formula. (Every function has a CNF representation!) 16

Reduction from CIRCUIT-SAT to 3-SAT Reduction: ? ? = ? , where ? is a 3-CNF defined as follows Circuit ? has variables ?1,?2, ,?? and AND/OR/NOT gates ?1, ,?? Assume without loss of generality that ?? is the output gate Formula ? has ? + ? variables, which we denote ?1, ,??,?1, ,?? Note: In ?, ?? is the name of a gate. In ?, ?? is the name of a variable 17

Reduction from CIRCUIT-SAT to 3-SAT For each AND/OR/NOT gate ?? in the circuit ?, define a 3-CNF ??: ?? ?? ?? ? ? ? ? ? ??= CHECK-OR ??,?,? ??= CHECK-NOT ??,? ??= CHECK-AND ??,?,? Reduction produces ?:= ?1 ?2 ?? ?? 18

Reduction example ?5 ?1= CHECK-NOT ?1,?1 = ?1 ?1 ( ?1 ?1) ?4 ?3 ?2= CHECK-NOT ?2,?2 = ?2 ?2 ?2 ?2 ?3= CHECK-AND ?3,?1,?2 = ?1 ?2 ?3 ?1 ?3 ?2 ?3 ?1 ?2 ?4= CHECK-AND ?4,?1,?2 = ?4 ?1 ?4 ?2 ?4 ?1 ?2 ?2 ?1 ?5= CHECK-OR ?5,?3,?4 = ?5 ?3 ?5 ?4 ?5 ?3 ?4 ? = ?1 ?1 ?3 ?1 ?2 ?5 ?4 ?1 ?1 ?2 ?2 ?4 ?1 ?5 ?3 ?4 ?5 ?2 ?2 ?4 ?2 ?4 ?1 ?2 ?5 ?3 ?3 ?1 ?3 ?2 19

YES maps to YES Claim: If the circuit ? is satisfiable, then the 3-CNF formula ? is also satisfiable Proof: We are assuming there is some ? {0,1}? such that ? ? = 1 For each ?, assign to ?? (the variable) the value that ?? (the gate) outputs when we evaluate ? on ? 20