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 \...
Top 50 recent answers are included
Related Tags
np-hardness × 660cc.complexity-theory × 325
graph-theory × 104
reference-request × 73
graph-algorithms × 69
ds.algorithms × 60
optimization × 46
reductions × 46
complexity-classes × 45
approximation-algorithms × 44
np-complete × 38
sat × 36
approximation-hardness × 34
np × 22
co.combinatorics × 20
partition-problem × 19
set-cover × 17
polynomial-time × 14
packing × 14
subset-sum × 14
graph-colouring × 13
directed-acyclic-graph × 12
time-complexity × 11
cg.comp-geom × 11
counting-complexity × 11