3-SAT & Clique

3-SAT ${\le }_p$ Clique

For a 3-SAT of $k$ clause, in this case, $k=3$, construct graph $G$, edge only exists when node are in different clause, and are not the negation of itself.

3-SAT is satisfiable $⟺$ There is a clique of size $k$

$(\Rightarrow )$: 3-SAT is satisfiable means there is at least one $1$ in each clause, so pick those nodes that have value $1$, they form a $k$ size clique(due to the way edges are constructed).

$(\Leftarrow )$: There is a clique of size $k$ means in each clause there is a boolean variable whose value is $1$, this makes 3-SAT satisfiable.

Links

• NP Completeness Definition
• SAT & 3-SAT

Reference

• Introduction to Algorithm