December 3, 200136 Reduction Example (6) SAT reduces to CLIQUE Two people know each other except if: they come from the same clause they represent t and t' for some variable t Clique of size 4  satisfiable assignment Satisfiable assignment  clique of size 4 (x, y, z) = (false, false, true) choose one true literal from each clause
{}