Hardness of mixed 3-SAT and 2-SAT formula

Question

It is well known that 3-SAT is $\sf NP$-complete , but 2-SAT is in $\sf P$. Let there be a formula with $n-1$ clauses with 2 literals each and only 1 clause with 3 literals.

We can solve this case in polynomial time, separating and solving in a brute force manner the 3 literal clause and then for each satisfying assignment try to solve the rest $n-1$ 2-literal clauses. This method can work till $O(\log n)$ clauses with 3 literals. If we consider a more general case with e.g $\frac{n}{2}$ clauses with 2 literals and $\frac{n}{2}$ clauses with 3 literals does the problem remain $\sf NP$-complete?

It is a bit confusing because we have a subproblem approximately the same size, implying it is difficult and another one roughly the same size implying it is easy. Is there probably a better method than the one I proposed?

Answer 1

First of all, these are not subproblems but different types of problems. In one your promise me that $n/2$ of the clauses only have 2 literals, and in the other your promise me that only $\log n$ of the clauses have 3 literals. These are simply different problems.

For the general case, it is easier to think about if you let $n = n_2 + n_3$ with $n_2$ being the number of 2-literal clauses, and $n_3$ being the number of 3-literal clauses. Let $f$ be a function such that $n = f(n_3)$. If $f$ is polynomial then the question is $NP$-complete by padding. If $f$ is super-polynomial (but not exponential) then we do not know the complexity of the problem. If $f$ is exponential then your approach of brute-force shows that the problem is in $P$.

Note that for every $f$ you could choose, you have a different problem. They just look similar.

Answer 2

If you have $\frac{n}{2}$ of the clauses with 3 literals the problem is trivially NP-complete by a reduction from 3-SAT.

Given a 3-SAT formula $\phi$ with $n$ clauses, ask whether $\psi = \phi \wedge_{i\in[n]}(y\lor \bar{y})$ is satisfiable (i.e. add $n$ dummy clauses with a new variable $y$).

Clearly, $|\psi|\leq 2\cdot|\phi|$, hence if your algorithm is polynomial in $|\psi|$ it is polynomial in $|\phi|$.

If you are looking for other smaller number of 3SAT clauses, keep in mind that the exponential time hypothesis is that $n$-clause 3SAT can't be solved in time $2^{o(k)}$.

This means that if ETH is true, and you have $n$ 3SAT clauses in your formula, and $poly(n)$ 2SAT clauses the running time of any algorithm will be strictly exponential. (without ETH, it's still NPC, as @Marzio mentioned).