Monotone 3-Satisfiability

I told Daniel when he gave me his Monotone Satisfiability reduction that the actual problem mentioned in G&J was Monotone 3-Satisfiability.  So he went off and did that reduction too.
The Problem:
Monotone 3 SAT. This is a more restrictive case of Monotone SAT

The Description:
Given an formula of clauses F' = \wedge_{i=1}^{n} C'_{i} where each clause in F' contains all negated or non-negated variables, and each clause C_{i} contains at most 3 variables. Does there exist an assignment of the variables so that F' is satisfied?

Example:

\\ F_{1} = (x_{1} \vee x_{3}) \wedge \\ (\neg x_{2} \vee \neg x_{3} \vee \neg x_{4}) \wedge  \\ (x_{3} \vee x_{2} \vee x_{4}) \wedge \\ ( \neg x_{3} \vee \neg x_{5} \vee \neg x_{1})
the following assignment satisfies F'_{1}:
\\  x_{1} \mapsto True\\ x_{2} \mapsto False\\ x_{3} \mapsto True\\ x_{4} \mapsto True\\ x_{5} \mapsto False
However:
\\ F_{2} = (\neg x_{1} \vee \neg x_{2} \vee \neg x_{3}) \wedge \\ (x_{1} \vee \neg x_{2} \vee \neg x_{3}) \wedge\\ (\neg x_{1} \vee x_{2} \vee \neg x_{3})\wedge \\ (\neg x_{1} \vee \neg x_{2} \vee x_{3})\wedge\\ (x_{1} \vee x_{2} \vee \neg x_{3})\wedge\\ (\neg x_{1} \vee x_{2} \vee x_{3})\wedge\\ (x_{1} \vee \neg x_{2} \vee x_{3})\wedge\\ (x_{1} \vee x_{2} \vee x_{3})
And the following is F_{2}' in Monotone  3SAT form:
\\ F_{2}' = (\neg x_{1} \vee \neg x_{2} \vee \neg x_{3}) \wedge \\ (\neg y_{1} \vee \neg x_{2} \vee \neg x_{3}) \wedge\\ (\neg x_{1} \vee \neg y_{2} \vee \neg x_{3})\wedge \\ (\neg x_{1} \vee \neg x_{2} \vee \neg y_{3})\wedge \\ (x_{1} \vee x_{2} \vee y_{3})\wedge\\ (y_{1} \vee x_{2} \vee x_{3})\wedge\\ (x_{1} \vee y_{2} \vee x_{3})\wedge\\ (x_{1} \vee x_{2} \vee x_{3}) \wedge \\ (y_{1} \vee x_{1}) \wedge (\neg y_{1} \vee \neg x_{1}) \wedge \\ (y_{1} \vee x_{2}) \wedge (\neg y_{2} \vee \neg x_{2})\wedge \\ (y_{1} \vee x_{3}) \wedge (\neg y_{3} \vee \neg x_{3})
are both unsatisfiable.

The reduction:
In the following reduction we are given an instance of 3SAT,
F = \wedge_{i=1}^{n} C_{i}. Here each clause is of the form:
C_{i} = x_{i1} \vee ... \vee x_{ik_i} where
k_{i} < 4
and each x_{ik_i} is a literal of the form \neg z_{l} \ or \ z_{l} .
We use the following construction to build an instance of Monotone  3 SAT out of the above instance of 3SAT :
In each clause C_{i} we have at most one literal, z_{l} \ or \ \neg z_{l} that is not of the same parity as the rest of the literals in the clause. For every such literal, we may preform the following substitution:
z_{l} \rightarrow \neg y_{l} \ or \ \neg z_{l} \rightarrow y_{l} this yields a modified clause C'_{i}.
Now we must be able to guarantee that z_{l} and y_{l} are mapped to opposite truth values, so we introduce the new clause:
C''_{i} \ = \ ( z_{l} \vee y_{l}) \wedge ( \neg z_{l} \vee \neg y_{l}) and conjunct it onto our old formula F producing a new formula F'.

For example:
C_{i} \ = \ (z_{l_1} \vee z_{l_2} \vee \neg z_{l_3}) so we preform the substitution
\neg z_{l_3} \rightarrow y_{l_3}
so C'_{i} \ = \ (z_{l_1} \vee z_{l_2} \vee y_{l_3}) and C''_{i} \ = \ (z_{l_3} \vee y_{l_3}) \wedge ( \neg z_{l_3} \vee \neg y_{l_3})

Now repeating this procedure will result in a new formula: F' = (\wedge_{i=1}^{n} C'_{i}) \wedge (\wedge_{k=1}^{m} C''_{k}).
We claim logical equivalence between the C_{i} \wedge C''_{i} and C'_{i} \wedge C''_{i} This is semantically intuitive as the C''_{i} clause requires all substituted literal y_{l} in C'_{i} to take the value opposite of z_{l} this was the stipulation for the substitution initially. It is also verifiable by truth table construction for:
\\ (z_{l_1} \vee z_{l_2} \vee \neg z_{l_3}) \wedge (z_{l_3} \vee y_{l_3}) \wedge ( \neg z_{l_3} \vee \neg y_{l_3}) \Leftrightarrow \\  (z_{l_1} \vee z_{l_2} \vee y_{l_3}) \wedge (z_{l_3} \vee y_{l_3}) \wedge ( \neg z_{l_3} \vee \neg y_{l_3})

True_{3SAT} \Rightarrow True_{Monotone \ 3 \ SAT}:
If there exists a truth assignment \phi_{F} that satisfies F, then we may extent this truth assignment to produce \phi_{G} which will satisfy
G = F \wedge (\wedge_{k=1}^{m} C''_{k}) by letting \phi_{G} (z_{l}) = \phi_{F} (x_{l}) for all l and letting \phi_{G}(y_{l}) = \neg \phi_{F}(z_{l}) for all l.
Obviously if F is satisfiable G must be by the above construction of \phi_{G}. So by the above claim we have that \phi_{G} will satisfy F'.
True_{Monotone \ 3 \ SAT} \Rightarrow True_{3SAT}:
Continuing from the above, if we have a truth assignment \phi_{F'} that satisfies F', then by the claim above it also must satisfy G. And F is a sub-formula of G so any truth assignment that satisfies G must also satisfy F.

(Back to me)

Difficulty: 4, since it’s a little harder than the regular Monotone Sat one.

2 responses to “Monotone 3-Satisfiability

  1. Is this even more restrictive version of Monotone 3-SAT (Monotone 2-3 SAT) too NP-Complete:
    1. All Clauses are monotone.
    2. All positive monotone clauses are of length 3.
    3. All negative monotone clauses are of length 2.

    • I don’t know, I haven’t heard of that variant. Let’s think about it.

      The reduction above gets you most of the way to where you want to go, with 2 exceptions:
      1) The transformation can create a positive monotone clause of length 2
      2) The original F may have a negative monotone clause of length 3.

      Of these, the second one worries me the most. Since 2-SAT is polynomial, we know that there isn’t a way to (in polynomial time) convert a set of clauses of length 3 into an equivalent set of clauses of length 2. (Because if we could, we’d have a reduction from 3SAT into 2SAT and P=NP). It seems like you’d have to do something like that to make this case work.

      So my gut feeling is that it’s not NP-Complete. but it’s possible that there is a different clever reduction out there that would do it.

Leave a Reply

Your email address will not be published. Required fields are marked *