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! 67/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