4
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Yes that is obvious, probably it was not clear enough in my question. With $O(n)$ 3 literal clauses the problem is obviously $NP-complete$. For $O(logn)$ 3 literal clauses $\in$ $P$. Can we say anything for the between cases? $\endgroup$ – Paramar Mar 3 '14 at 17:02
  • $\begingroup$ We can say that they're at least as hard as the corresponding instances of padded 3-SAT. $\hspace{.54 in}$ $\endgroup$ – user12859 Mar 3 '14 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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