2
$\begingroup$

I was thinking that in exact 3sat there's only one pattern that can be a contradiction, namely $$ (a \vee b \vee c) \wedge (a \vee b \vee \neg c) \wedge (a \vee \neg b \vee c) \wedge (a \vee \neg b \vee \neg c) \wedge \\ (\neg a \vee b \vee c) \wedge (\neg a \vee b \vee \neg c) \wedge (\neg a \vee \neg b \vee c) \wedge (\neg a \vee \neg b \neg c) $$ $(a,b,c)$ are placeholders for e.g. $(a=x1, b=x33, c=x14)$. If there's no contradiction, then it must be satisfiable. Thus, if I can't find such a pattern, then it must be satisfiable. Meaning that if I find a term like $(x1 \vee x3 \vee \neg x5)$ then there must also exist a term $(\neg x1 \vee x3 \vee \neg x5)$, otherwise $(x1 \vee x3 \vee \neg x5)$ isn't part of a contradiction.

Obviously there must be some non-obvious error here, otherwise the problem wouldn't be hard. But I can't seem to find the fault?

$\endgroup$
1
$\begingroup$

It is not the only one. Each triplet reduces certain number of possibilities. You can use $a_1$ and $a_2$ to construct such triplets, that $c$ can't be zero, and then construct using $a_3$ and $a_4$ such triplets, that $c$ can't be one.

$(a_1 \lor a_2 \lor c) \land(a_1 \lor \neg a_2 \lor c) \land(\neg a_1 \lor a_2 \lor c) \land(\neg a_1 \lor \neg a_2 \lor c) $

$\land$

$(a_3 \lor a_4 \lor \neg c) \land(a_3 \lor \neg a_4 \lor \neg c) \land(\neg a_3 \lor a_4 \lor \neg c) \land(\neg a_3 \lor \neg a_4 \lor \neg c)$

And this also does not cover the whole problem, you can create complicated nets of formulas, where each reduces some possibilities for some varibles and cleverly connecting them together until no possibility satisfying the whole formula is left.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.