1
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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