New answers tagged


There are many ways to reduce CLIQUE to SAT. Probably the simplest is as follows. Suppose that we have a graph $G = (V,E)$, and interested in a $k$-clique. We will have $k|V|$ variables $x_{iv}$, whose intended meaning is "the $i$th vertex of the clique is $v$". The constraints are: There is an $i$th vertex: for all $1 \leq i \leq k$, $\bigvee_{v \in V} x_{...

Top 50 recent answers are included