My solution to this NPC problem (1) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>EE - 电子工程

My solution to this NPC problem (1)

My solution to this NPC problem (1)# EE - 电子工程

r*r2002-12-12 08:12

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*w2002-12-12 08:12

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