Approach:reduction Given a3-SAT formula=C1∧…∧Ck,we construct a graph G s.t. if is satisfiable,then G has a clique of size k. if o is unsatisfiable,then G has no clique of size k. Note:k is the number of clauses of If you can solve the Clique problem,then you can also solve the 3-SAT problem 21Approach: reduction ◼ Given a 3-SAT formula 𝜑 = 𝐶1 ∧ ⋯ ∧ 𝐶𝑘, we construct a graph 𝐺 s.t. ❑ if 𝜑 is satisfiable, then 𝐺 has a clique of size 𝑘. ❑ if 𝜑 is unsatisfiable, then 𝐺 has no clique of size ≥ 𝑘. ❑ Note: 𝑘 is the number of clauses of 𝜑. ◼ If you can solve the Clique problem, then you can also solve the 3-SAT problem. 21