# Complexity of the $(3,2)_s$ SAT problem?

Let define the $(3,2)_s$ SAT problem : Given $F_3$, a satisfiable 3-CNF formula, and $F_2$, a 2-CNF formula ($F_3$ and $F_2$ are defined on the same variables). Is $F_3 \wedge F_2$ satisfiable?

What is the complexity of this problem ? (Has it been studied before ?)

Let $\varphi$ be an arbitrary CNF formula (an instance of SAT). Consider $\varphi \lor y$, where $y$ is a fresh variable; obviously, this formula is satisfiable (you can simply set $y$ to true). Now convert $\varphi \lor y$ to 3-CNF, using any standard method, and let $\psi$ denote the result. Note that $\psi$ is a satisfiable 3-CNF formula, so we can let $F_3 = \psi$. Now, let $F_2 = \neg y$. Notice that $F_3 \land F_2$ is satisfiable if and only if $\varphi$ is. Therefore, the $(3,2)_s$ SAT problem is at least as hard as SAT. Also, it is clearly no harder than SAT. Therefore, it is exactly as difficult as SAT.
• @TysonWilliams, yup, sure, we could do that too. Is there any sense in which reducing from 3SAT would be better? It doesn't seem to make any significant difference either way, as far as I can see. Reducing from 3SAT doesn't seem to make the reduction any simpler. Even if $\varphi$ is a 3-CNF formula, $\varphi \lor y$ won't be, so you still need to convert to 3-CNF either way. – D.W. Jul 16 '13 at 0:30
Here is a paper by Porshen and Speckenmayer : Satisfiability of mixed Horn formulas which shows that even when $F_3$ is Horn, the problem of deciding the satisfiability of $F_3 \wedge F_2$ is NP-complete.