# Complexity of this variant of the Monotone(+,2−) -SAT problem?

In this post,Monotone$$(+, 2^-)$$-SAT problem is defined as follows:

Given a monotone CNF formula $$F^+$$, where each variable appears exactly once (as a positive literal), and a monotone 2-CNF formula $$F_2^-$$ defined on the same variables as $$F^+$$, where all variables are negated. Is $$F^+ \land F_2^-$$ satisfiable ?), let us define the Monotone$$(+, 2^-)$$-SAT problem:

Given a monotone CNF formula $$F^+$$, where each variable appears exactly once (as a positive literal), and a monotone 2-CNF formula $$F_2^-$$ defined on the same variables as $$F^+$$, where all variables are negated. Is $$F^+ \land F_2^-$$ satisfiable ?

Consider this variant of Monotone(+,2−)-SAT problem where we restrict the number of clause of $$F^+$$ to be 2 and the width of these 2 clause can be anything ,that means that every instance of positive literal appears in only 2 clause.

Is this variant also NP-complete? I don't see any direct reduction from the main problem to this variant ,so does there exist any reduction or is it solvable in polynomial time?

• Some text in the post appears to be duplicated (2nd and 3rd paragraph). Perhaps you might like to edit your post?
– D.W.
Feb 6, 2023 at 18:27
• Yes ,its from the post mentioned above.
– Anuj
Feb 7, 2023 at 2:01
• what specific edits do i need to make?
– Anuj
Feb 7, 2023 at 2:03

It is in P. Suppose the first clause of $$F^+$$ has $$k_1$$ variables, and the second clause has $$k_2$$ variables. Then there are $$k_1 k_2$$ ways to pick one variable from the first clause, and one variable from the second clause. For each such way, set those variables to true in $$F_2^-$$ (i.e., replace those variables with true, and simplify). The result is a 2-CNF formula, and you can test satisfiability of it in linear time. Check whether the result is satisfiable. If it is, then you obtain a satisfying assignment for $$F^+ \land F_2^-$$. Repeat once for each of these $$k_1 k_2$$ possibilities.