Instance of Subset-Sum 1000 100 = v1 1000 010 = v1' 0100 100 = v2 0100 011 = v2' 0010 001 = v3 0010 010 = v3' 0001 001 = v4 0001 100 = v4' 0000 100 = s1 0000 200 = s1' 0000 010 = s2 0000 020 = s2' 0000 001 = s3 0000 002 = s3' 1111 444
v1+v2'+v3'+v4'+s1'+s2'+s3+s3' = 1111 444 corresponds to x1 true, x2 false, x3 false, x4 false(Edited: 2018-04-25)
! - | x_1 | x_2 | x_3 | x_4 | C_1 | C_2 | C_3 |
---|---|---|---|---|---|---|---|
v_1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
v_1' | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
v_2 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
v_2' | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
v_3 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
v_3' | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
v_4 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
v_4' | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
s_1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
s_1' | 0 | 0 | 0 | 0 | 2 | 0 | 0 |
s_2 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
s_2' | 0 | 0 | 0 | 0 | 0 | 2 | 0 |
s_3 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
s_3' | 0 | 0 | 0 | 0 | 0 | 0 | 2 |
- | 1 | 1 | 1 | 1 | 4 | 4 | 4 |
x1 x2 x3 x4 C1 C2 C3 v1 = 1 0 0 0 1 0 0 v1'= 1 0 0 0 0 1 0 v2 = 0 1 0 0 1 0 0 v2'= 0 1 0 0 0 1 1 v3 = 0 0 1 0 0 0 1 v3'= 0 0 1 0 0 1 0 v4 = 0 0 0 1 0 0 1 v4'= 0 0 0 1 1 0 0 s1 = 0 0 0 0 1 0 0 s1'= 0 0 0 0 2 0 0 s2 = 0 0 0 0 0 1 0 s2'= 0 0 0 0 0 2 0 s3 = 0 0 0 0 0 0 1 s3'= 0 0 0 0 0 0 2 1 1 1 1 4 4 4
x1 x2 x3 x4 C1 C2 C3 v1 = 1 0 0 0 1 0 0 v1'= 1 0 0 0 0 1 0 v2 = 0 1 0 0 1 0 0 v2'= 0 1 0 0 0 1 1 v3 = 0 0 1 0 0 0 1 v3'= 0 0 1 0 0 1 0 v4 = 0 0 0 1 0 0 1 v4'= 0 0 0 1 1 0 0 s1 = 0 0 0 0 1 0 0 s1'= 0 0 0 0 2 0 0 s2 = 0 0 0 0 0 1 0 s2'= 0 0 0 0 0 2 0 s3 = 0 0 0 0 0 0 1 s3'= 0 0 0 0 0 0 2 1 1 1 1 4 4 4
x1 x2 x3 x4 C1 C2 C3 v1 1 0 0 0 1 0 0 v1' 1 0 0 0 0 1 0 v2 0 1 0 0 1 0 0 v2' 0 1 0 0 0 1 1 v3 0 0 1 0 0 0 1 v3' 0 0 1 0 0 1 0 v4 0 0 0 1 0 0 1 v4' 0 0 0 1 1 0 0 s1 0 0 0 0 1 0 0 s1' 0 0 0 0 2 0 0 s2 0 0 0 0 0 1 0 s2' 0 0 0 0 0 2 0 s3 0 0 0 0 0 0 1 s3' 0 0 0 0 0 0 2 1 1 1 1 4 4 4
Let x1 = T x2 = F x3 = T x4 = T Pick v1 + v2' + v3 + v4 + s1' + s2'+ s3 + s3' = 1111 444
Given : φ=C1∧C2∧C3 where C1=(x1 ∨ x2 ∨ ¬x4), C2=(¬x1 ∨ ¬x2 ∨ ¬x3), C3=(¬x2 ∨ x3 ∨ x4)
x1 x2 x3 x4 C1 C2 C3 v1 1 0 0 0 1 0 0 v1' 1 0 0 0 0 1 0 v2 0 1 0 0 1 0 0 v2' 0 1 0 0 0 1 1 v3 0 0 1 0 0 0 1 v3' 0 0 1 0 0 1 0 v4 0 0 0 1 0 0 1 v4' 0 0 0 1 1 0 0 s1 0 0 0 0 1 0 0 s1' 0 0 0 0 2 0 0 s2 0 0 0 0 0 1 0 s2' 0 0 0 0 0 2 0 s3 0 0 0 0 0 0 1 s3' 0 0 0 0 0 0 2 1 1 1 1 4 4 4
Solution : v1+v2'+v3'+v4'+s1'+s2'+s3+s3' Hence x1 = true x2 = false x3 = false x4 = false(Edited: 2018-04-29)
x1 x2 x3 x4 C1 C2 C3 v1 = 1 0 0 0 1 0 0 v1'= 1 0 0 0 0 1 0 v2 = 0 1 0 0 1 0 0 v2'= 0 1 0 0 0 1 1 v3 = 0 0 1 0 0 0 1 v3'= 0 0 1 0 0 1 0 v4 = 0 0 0 1 0 0 1 v4'= 0 0 0 1 1 0 0 s1 = 0 0 0 0 1 0 0 s1'= 0 0 0 0 2 0 0 s2 = 0 0 0 0 0 1 0 s2'= 0 0 0 0 0 2 0 s3 = 0 0 0 0 0 0 1 s3'= 0 0 0 0 0 0 2 1 1 1 1 4 4 4
Let x1 = false, x2 = true, x3 = false, x4 = true . Then we pick v1'+ v2 + v3' + v4 + s1' + s2 + s2' + s3' = 1111 444