r********r
发帖数: 11248 | 1 1) NP part, that's obvious.
2) NP-hard part: reduce Partition Problem to this Half-3-CNF problem
Construction:
given an input instance of the Parition Problem, a set S of n integers,
we can contruct an instance for Half-3-CNF problem as follows:
for example, if S = {1, 2, 3, 6}, we make a 3-CNF (where * is AND, + is OR)
Q = (x1 + x100 + x200) *
(x2 + x100 + x200) * (x2 + x100 + x200) *
(x3 + x100 + x200) * (x3 + x100 + x200) * (x3 + x100 + x200) *
(x4 + x100 + x200) * (x4 + x10 | f*****w
发帖数: 16 | 2 I think your reduction is not polynomial, because the value of the integers
can be exponential, thus your contructed instance will be exponential
also, even 3CNF requires the three literals be distinct, as pointed out by
wenyia, my original method can still be salvaged, still reduce from 3CNF-SAT:
3CNF-SAT: m clauses C1, C2, ..., Cm
half 3CNF-SAT: m old clauses plus
m clauses of (z1 V z2 V z3)
1. if original problem is satisfiable, set z1, z2, z3 to 0
2. if constructed instance is half sa |
|
