I am supposed to show that

$3SAT$ $\rightarrow$ Every clause hast exact $3$ literals

is polynomial reducible to

$MSAT$ $\rightarrow$ At least half of every clauses' literals are true

Let $F$ be a fulfilling configuration of $3SAT$, i.e. $F$ = $C_1 \wedge ... \wedge C_n$, where $C$ contains exactly $3$ literals. I tried to reduce $3SAT$ to $MSAT$ by introducing $2$ new variables $a_1$ and $a_2$ and add them to each clause of $F$. This reduction formula would then be $f(F) = g(C_1) \wedge ... \wedge g(C_n)$ with $g(C) = l_1 \vee l_2 \vee l_3 \vee a_1 \vee a_2$. Now I am a little bit stuck, could I simply consider that $a_1$ and $a_2$ are always true? Or do I have distinguish between the $4$ cases where $a_1$ and $a_2$ are true, $a_1$ is not true, but $a_2$ is true and so on? If so, it is not possible that half of the literals of each clause are true anymore. In this case it would be not a valid $MSAT$ instance?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.