NP-completeness ■k-SAT is NP-complete,.for any k≥3. NP-complete: o In NP All other problems in NP can be reduced to it in poly.time NP-complete problems are the hardest ones in NP. ■3-SAT is in NP: witness---satisfying assignment Verification:evaluate formula with variables assigned by [Cook-Levin]3-SAT is NP-complete
NP-completeness ◼ k-SAT is NP-complete, for any k ≥ 3. ◼ NP-complete: ❑ In NP ❑ All other problems in NP can be reduced to it in poly. time ◼ NP-complete problems are the hardest ones in NP. ◼ 3-SAT is in NP: ❑ witness --- satisfying assignment A ❑ Verification: evaluate formula with variables assigned by A ◼ [Cook-Levin] 3-SAT is NP-complete
How about 2-SAT? While 3-SAT is the hardest in NP.2-SAT is solvable in polynomial time. Here we present a very simple randomized algorithm,which has polynomial expected running time
How about 2-SAT? ◼ While 3-SAT is the hardest in NP, 2-SAT is solvable in polynomial time. ◼ Here we present a very simple randomized algorithm, which has polynomial expected running time
Algorithm for 2-SAT 2SAT:each clause has two variables/negations (x1V2)∧(2VX3)∧(-x4Vx3)∧(xVx1) Alg [Papadimitriou]: 口 Pick any assignment X1,X23X3,X4,X5 ▣Repeat O(n2)time ①1,0,1， If all satisfied,done Else Pick any unsatisfied clause Pick one of the two literals each with probability,and flip the assignment on that variable
Algorithm for 2-SAT ◼ 2SAT: each clause has two variables/negations ◼ Alg [Papadimitriou]: ❑ Pick any assignment ❑ Repeat O(n2 ) time ◼ If all satisfied, done ◼ Else ❑ Pick any unsatisfied clause ❑ Pick one of the two literals each with ½ probability, and flip the assignment on that variable (x1∨x2 )∧(x2∨¬x3 ) ∧(¬x4∨x3 ) ∧(x5∨x1 ) x1 , x2 , x3 , x4 , x5 0, 1, 0, 1, 0 1
Analysis (XVX2)A(X2V-X3)A(-X4VX3)A(X5VX1) ▣ X1,X2,X3,X4,X5 @1,0,1,@ If unsatisfiable:never find an satisfying assignment If satisfiable,there exists a satisfying assignment x If our initially picked assignment x'is satisfying,then done. Otherwise,for any unsatisfied clause,at least one of the two variables is assigned a value different than that in x Randomly picking one of the two variables and flipping its value increases correct assignments by 1 w.p
Analysis ◼ (x1∨x2 )∧(x2∨¬x3 ) ∧(¬x4∨x3 ) ∧(x5∨x1 ) ❑ x1 , x2 , x3 , x4 , x5 ❑ 0, 1, 0, 1, 0 ◼ If unsatisfiable: never find an satisfying assignment ◼ If satisfiable, there exists a satisfying assignment x ❑ If our initially picked assignment x’ is satisfying, then done. ❑ Otherwise, for any unsatisfied clause, at least one of the two variables is assigned a value different than that in x ❑ Randomly picking one of the two variables and flipping its value increases # correct assignments by 1 w.p. ≥ ½
Analysis (continued) Consider a line of n+1 points,where k represents "we've assigned k variables correctly' "correctly":the same way as x Last slide:Randomly picking one of the two variables and flipping its value increases correct assignments by 1 w.p. Thus the algorithm is actually a random walk on the line of n+1 points,with Pr[going right]=2. Hitting time (in):O(n2) So by repeating this flipping process O(n2)steps, we'll reach x with high probability
Analysis (continued) ◼ Consider a line of n+1 points, where k represents “we’ve assigned k variables correctly” ❑ “correctly”: the same way as x ◼ Last slide: Randomly picking one of the two variables and flipping its value increases # correct assignments by 1 w.p. ≥ ½ ◼ Thus the algorithm is actually a random walk on the line of n+1 points, with Pr[going right] ≥ ½. ❑ Hitting time (i → n): O(n2 ) ◼ So by repeating this flipping process O(n2 ) steps, we’ll reach x with high probability