# np complete – NP-completeness of variant SAT: SAT-5Clauses

It is unknown whether the problem is $$NP$$-complete. In particular, you problem is non-trivial and it is in $$P$$. Therefore it is $$NP$$-complete if and only if $$P=NP$$.

To see that your problem is in $$P$$ you can consider the following “brute-force” algorithm.
Let $$n$$ be the number of variables and $$n$$ be the number of clauses.

If it is possible to simultaneously satisfy $$5$$ clauses, then there are $$5$$ literals that are true and belong to different clauses.

You can then explicitly consider all subsets of $$min{n, 5}$$ variables and, for each subset $$S$$, try all possible (constantly many) truth assignments to the variables in $$S$$.

For each of these $$O(n^5)$$ (partial) truth assignments, check whether at least $$5$$ clauses are satisfied. This can in constant time after a linear-time preprocessing of the input instance.

The overall time required is then $$O(mn + n^5)$$ where $$O(mn)$$ is an upper bound on the size of the instance.

Posted on Categories Articles