7/8-approximation of 3SAT Since 3SAT appears too hard in its full generality,let's aim lower. 3SAT asks whether there is an assignment satisfying all clauses. ■ Can you find an assignment satisfying half of the clauses? Let's run an example where you give an input instance you give a solution! 6
7/8-approximation of 3SAT ◼ Since 3SAT appears too hard in its full generality, let’s aim lower. ◼ 3SAT asks whether there is an assignment satisfying all clauses. ◼ Can you find an assignment satisfying half of the clauses? ◼ Let’s run an example where ❑ you give an input instance ❑ you give a solution! 6
Observation What did we just do? How did we assign values to variables? For each variable xi,we choose a number from {0,1}. How good is this assignment? Result:out 5;out 5
Observation ◼ What did we just do? ◼ How did we assign values to variables? ◼ For each variable 𝑥𝑖 , we ___ choose a number from {0,1}. ◼ How good is this assignment? ❑ Result: __ out 5; __ out 5. 7
Why? For each clause,there are 8 possible assignments for these three variables,and only 1 fails. ▣ E.g.x1V x2 Vx3:only (x1,x2,x3)=(0,0,0)fails. E.g.V x2Vx3:only (x1,x2,x3)=(1,0,1)fails. Thus if you assign randomly,then with each clause fails with probability only 1/8. Thus the expected number of satisfied clauses is 7m/8. ▣ m:number of clauses 8
Why? ◼ For each clause, there are 8 possible assignments for these three variables, and only 1 fails. ❑ E.g. 𝑥1 ∨ 𝑥2 ∨ 𝑥3: only 𝑥1, 𝑥2, 𝑥3 = (0,0,0) fails. ❑ E.g. 𝑥1 ∨ 𝑥2 ∨ 𝑥3 : only 𝑥1, 𝑥2, 𝑥3 = (1,0,1) fails. ◼ Thus if you assign randomly, then with each clause fails with probability only 1/8. ◼ Thus the expected number of satisfied clauses is 7𝑚/8. ❑ 𝑚: number of clauses 8
Formally-algorithm Repeat Pick a random a e {0,17. See how many clauses the assignment x a satisfies. Return a if it satisfies 7m/8 clauses. This is a Las Vegas algorithm: The running time is not fixed.It's a random variable. 口 When the algorithm terminates,it always gives a correct output. The complexity measure is the expected running time. 9
Formally - algorithm ◼ Repeat Pick a random 𝑎 ∈ 0,1 𝑛 . See how many clauses the assignment 𝑥 = 𝑎 satisfies. Return 𝑎 if it satisfies ≥ 7𝑚/8 clauses. ◼ This is a Las Vegas algorithm: ❑ The running time is not fixed. It’s a random variable. ❑ When the algorithm terminates, it always gives a correct output. ❑ The complexity measure is the expected running time. 9
Formally-analysis Define a random variable Y for each clause i. If clause i is satisfied,then Yi 1,otherwise Yi 0. Define another random variable Y =i Yi Y has a clear meaning:number of satisfied clauses What's expectation of Y? 10
Formally - analysis ◼ Define a random variable 𝑌𝑖 for each clause 𝑖. ❑ If clause 𝑖 is satisfied, then 𝑌𝑖 = 1, otherwise 𝑌𝑖 = 0. ◼ Define another random variable 𝑌 = σ𝑖 𝑌𝑖 ❑ 𝑌 has a clear meaning: number of satisfied clauses ◼ What’s expectation of 𝑌? 10