|
2 | typo fix | ||
|
I think 3SAT can be reduced to your problem, since ($a_1$ OR $a_2$ OR $a_3$) AND ($b_1$ OR $b_2$ OR $b_3$) AND ($c_1$ OR $c_2$ OR $c_3$) AND ... is satisfiable iff (NOT $A_1$ OR $a_2$ OR $a_3$) AND ($A_1$ OR $a_1$) AND (NOT $B_1$ OR $b_2$ OR $b_3$) AND ($B_1$ OR $b_1$) AND (NOT $C_1$ OR $c_2$ OR $c_3$) AND ($C_1$ OR $C_1$) c_1$) AND ... is. |
||||
|
|
1 |
|
||
|
I think 3SAT can be reduced to your problem, since ($a_1$ OR $a_2$ OR $a_3$) AND ($b_1$ OR $b_2$ OR $b_3$) AND ($c_1$ OR $c_2$ OR $c_3$) AND ... is satisfiable iff (NOT $A_1$ OR $a_2$ OR $a_3$) AND ($A_1$ OR $a_1$) AND (NOT $B_1$ OR $b_2$ OR $b_3$) AND ($B_1$ OR $b_1$) AND (NOT $C_1$ OR $c_2$ OR $c_3$) AND ($C_1$ OR $C_1$) AND ... is. |
||||
