My solution to this NPC problem (2)# EE - 电子工程
r*r
1 楼
Now we want to prove if S \in PARITION <==> Q \in Half-3-CNF
Proof: ====>
if S \in PARITION, then there is a subset of S, let's say
S1 ={1, 2, 3}, the sum of S1 is equal to the sum of S-S1 = {6}.
Then we can assign: x100 and x200 to 0, and all the xi corresponding
to S1 as 1, all xi corresponding to S- S1 as 0. In this example, we
set x1, x2, x3 to 1, x4 to 0, we can see the resulted Q belongs to Half-3-CNF.
<====
If this Q is a Half-3-CNF problem, meaning we can find an assignment making
hal
Proof: ====>
if S \in PARITION, then there is a subset of S, let's say
S1 ={1, 2, 3}, the sum of S1 is equal to the sum of S-S1 = {6}.
Then we can assign: x100 and x200 to 0, and all the xi corresponding
to S1 as 1, all xi corresponding to S- S1 as 0. In this example, we
set x1, x2, x3 to 1, x4 to 0, we can see the resulted Q belongs to Half-3-CNF.
<====
If this Q is a Half-3-CNF problem, meaning we can find an assignment making
hal