New answers tagged np-hardness
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 \...
- 1,398
Top 50 recent answers are included