0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.