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
