My solution to this NPC problem (1)# EE - 电子工程
r*r
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
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