# NP-completeness of variant SAT: SAT-5Clauses

I'm solving Problem 14.4 of What can be computed?.

14.4 Define the decision problem SAT-5CLAUSES as follows. The input is a Boolean formula B in CNF. The solution is “yes” if it is possible to simultaneously satisfy at least 5 of B’s clauses. Is SAT-5CLAUSES NP-complete? Give a rigorous proof of your answer.

Is there any suggestion to solve this problem?

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