2022 Developer Survey is open! Take survey.

New answers tagged

2 votes
Accepted

Complexity of the Complete (3,2) SAT problem?

Consider the standard reduction from 3-coloring to SAT: for each vertex $v \in V$ we introduce three variables, $v_R,v_G,v_B$, add a clause $(v_R \vee v_G \vee v_B)$, and clauses $(\lnot v_R \vee \...
user avatar
  • 1,398

Top 50 recent answers are included