[Solved]: Hardness of mixed 3-SAT and 2-SAT formula

Problem Detail: 

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?

Asked By : Paramar

Answered By : Artem Kaznatcheev

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22233

3.2K people like this

 Download Related Notes/Documents