<p>If <span class="math-container">$F_3$</span> and <span class="math-container">$F_2$</span> are both monotone, satisfiability can be checked in polynomial time (or even in coNLOGTIME), as <span class="math-container">$F_3\land F_2$</span>, which is also monotone, is satisfiable iff it is satisfied by the <span class="math-container">$\vec1$</span> assignment, that is, iff it does not contain the empty clause.</p>
<p>If one of the formulas is allowed to be monotone and the other one negated monotone (i.e., having only negative literals), then satisfiability of <span class="math-container">$F_3\land F_2$</span> is NP-complete: given a 3-CNF <span class="math-container">$F$</span> in variables <span class="math-container">$x_1,\dots,x_n$</span>, let <span class="math-container">$F_3$</span> be the monotone 3-CNF obtained from <span class="math-container">$F$</span> by replacing all negative literals <span class="math-container">$\neg x_i$</span> with new variables <span class="math-container">$y_i$</span>, and let <span class="math-container">$F_2=\bigwedge_i(\neg x_i\lor\neg y_i)$</span>. Then <span class="math-container">$F$</span> is equisatisfiable with <span class="math-container">$F_3\land F_2$</span>.</p>
<p>In particular, if <span class="math-container">$(\vec x,\vec y)$</span> is a satisfying assignment for <span class="math-container">$F_3\land F_2$</span>, then for each <span class="math-container">$i$</span>, at most one of <span class="math-container">$x_i$</span> or <span class="math-container">$y_i$</span> gets value <span class="math-container">$1$</span>, that is, <span class="math-container">$y_i\le\neg x_i$</span>. Thus, if we modify the assignment so that <span class="math-container">$y_i:=\neg x_i$</span>, it will still satisfy <span class="math-container">$F_3$</span> as it is monotone. It follows that <span class="math-container">$\vec x$</span> satisfies the original formula <span class="math-container">$F$</span>.</p>

CC BY-SA 4.0
2020-09-05T11:09:37.447Z
2020-09-05T11:09:37.447Z
Emil Jeřábek
<p>Context: Refering to the  question: <a href="https://cstheory.stackexchange.com/a/18384/6346">Complexity of the <span class="math-container">$(3,2)_s$</span> SAT problem?</a> and since the paper by Porshen and Speckenmayer : <a href="http://math.bme.hu/%7Ehujter/porsch07.pdf" rel="nofollow noreferrer">Satisfiability of mixed Horn formulas</a>, we know that even when <span class="math-container">$F_3$</span> is Horn, the problem of deciding the satisfiability of <span class="math-container">$F_3 \wedge F_2$</span> is NP-complete - where <span class="math-container">$F_3$</span> and <span class="math-container">$F_2$</span> are respectively 3-CNF and 2-CNF formulas.</p>
<p>I am wondering if there exist some cases where <span class="math-container">$F_3 \wedge F_2$</span> is easy to decide.
Hence my question:</p>
<p>Let <span class="math-container">$F_3$</span> a 3-CNF containing only clauses with exactly 3 different literals and <span class="math-container">$F_2$</span> a 2-CNF defined on the same variables as <span class="math-container">$F_3$</span>.</p>
<p><strong>What is the complexity of deciding the satisfiability of <span class="math-container">$F_3 \wedge F_2$</span> when <span class="math-container">$F_3$</span> and <span class="math-container">$F_2$</span> are both monotone?</strong></p>
<p>Thank you.</p>

CC BY-SA 4.0
2020-09-05T06:51:00.087Z
Anytime $F_2$ has few solutions, it is easy to find them, and this reduces the search space for $F_3$. More generally, I would expect some properties on the implication graph that $F_2$ represents to ensure that a tweaked DPLL runs fast. In this context, "few solutions" can probably be understood as "few strongly connected components".
xavierm02
CC BY-SA 4.0
2020-09-05T20:32:07.733Z
I am confused about what assumptions you are making.  Should I assume both 1 and 2; or are those two separate questions?  If those are separate questions, it might be better to ask them separately.  Should I assume $F_3$ is Horn in both of those cases, or was that just a motivating comment that should be ignored for the rest of the post?
D.W.
CC BY-SA 4.0
2020-09-05T20:38:30.847Z
@D.W. That is two separate questions. The Horn introduction was just a motivating comment and should be ignored for the rest of the post. Sorry for the confusion.
Xavier Labouze
CC BY-SA 4.0
2020-09-05T20:39:40.543Z
I encourage you to [edit] the question to make that clearer, and to post the second question separately.  As you can see, you already got an answer that addresses the first of the two questions but not the second, so this will now be treated as an "answered" question and might be less likely to get attention for the second question.
D.W.
CC BY-SA 4.0
2020-09-05T20:48:47.810Z
@D.W. Just did it. I removed the second part of the question since the first part is NP-complete - so is the second part.
Xavier Labouze
<np-hardness><sat><monotone>
3-SAT mixed with 2-SAT formulas
Xavier Labouze
# 3-SAT mixed with 2-SAT formulas

(Asked by: username_0 on 2020-09-04)

Context: Refering to the question: [Complexity of the $(3,2)\_s$ SAT problem?](https://cstheory.stackexchange.com/a/18384/6346) and since the paper by Porshen and Speckenmayer : [Satisfiability of mixed Horn formulas](http://math.bme.hu/%7Ehujter/porsch07.pdf), we know that even when $F\_3$ is Horn, the problem of deciding the satisfiability of $F\_3 \wedge F\_2$ is NP-complete - where $F\_3$ and $F\_2$ are respectively 3-CNF and 2-CNF formulas.

I am wondering if there exist some cases where $F\_3 \wedge F\_2$ is easy to decide.
Hence my question:

Let $F\_3$ a 3-CNF containing only clauses with exactly 3 different literals and $F\_2$ a 2-CNF defined on the same variables as $F\_3$.

**What is the complexity of deciding the satisfiability of $F\_3 \wedge F\_2$ when $F\_3$ and $F\_2$ are both monotone?**

Thank you.

**Tags:** np-hardness, sat, monotone
> **Comments:**
> **username_1**: Anytime $F_2$ has few solutions, it is easy to find them, and this reduces the search space for $F_3$. More generally, I would expect some properties on the implication graph that $F_2$ represents to ensure that a tweaked DPLL runs fast. In this context, "few solutions" can probably be understood as "few strongly connected components".  
> **username_2**: I am confused about what assumptions you are making.  Should I assume both 1 and 2; or are those two separate questions?  If those are separate questions, it might be better to ask them separately.  Should I assume $F_3$ is Horn in both of those cases, or was that just a motivating comment that should be ignored for the rest of the post?  
> **username_0**: @D.W. That is two separate questions. The Horn introduction was just a motivating comment and should be ignored for the rest of the post. Sorry for the confusion.  
> **username_2**: I encourage you to [edit] the question to make that clearer, and to post the second question separately.  As you can see, you already got an answer that addresses the first of the two questions but not the second, so this will now be treated as an "answered" question and might be less likely to get attention for the second question.  
> **username_0**: @D.W. Just did it. I removed the second part of the question since the first part is NP-complete - so is the second part.  

---

## 1 answers

### Answer by username_3 on 2020-09-05. Score: 7 | Accepted answer

If $F\_3$ and $F\_2$ are both monotone, satisfiability can be checked in polynomial time (or even in coNLOGTIME), as $F\_3\land F\_2$, which is also monotone, is satisfiable iff it is satisfied by the $\vec1$ assignment, that is, iff it does not contain the empty clause.

If one of the formulas is allowed to be monotone and the other one negated monotone (i.e., having only negative literals), then satisfiability of $F\_3\land F\_2$ is NP-complete: given a 3-CNF $F$ in variables $x\_1,\dots,x\_n$, let $F\_3$ be the monotone 3-CNF obtained from $F$ by replacing all negative literals $\neg x\_i$ with new variables $y\_i$, and let $F\_2=\bigwedge\_i(\neg x\_i\lor\neg y\_i)$. Then $F$ is equisatisfiable with $F\_3\land F\_2$.

In particular, if $(\vec x,\vec y)$ is a satisfying assignment for $F\_3\land F\_2$, then for each $i$, at most one of $x\_i$ or $y\_i$ gets value $1$, that is, $y\_i\le\neg x\_i$. Thus, if we modify the assignment so that $y\_i:=\neg x\_i$, it will still satisfy $F\_3$ as it is monotone. It follows that $\vec x$ satisfies the original formula $F$.


---

