# Variation of MAX 3-SAT

Suppose we are given a 3CNF, and we want to know whether k clauses from this 3CNF can be satisfied (k being any natural number)?

I'm trying to think of an efficient algorithm to solve this problem. This is sort of a variation of the MAX 3-SAT, but with a fixed k. If we have m clauses, checking naively would get $\binom{m}{k}$ comparisons, but this seems factorial (if we approximate with Sterling's formula, exponential) complexity.

What could be an efficient way to check this? I must be missing something. Thanks.

• Is $k$ a fixed constant? If so, $\binom{m}{k}=O(m^k)$ – David Richerby Mar 30 '16 at 3:18

If ​ 2$\cdot$k ≤ #_of_non-empty_clauses ​ then YES, since the expected number of those clauses satisfied by a random assignment is at least half of #_of_non-empty_clauses,
Thus, your problem can be kernelized in linear time into less than 2$\cdot$k clauses.
This is the decision version of MAX-3SAT, which is known to be NP-complete. In particular, if you choose $k = m$ then you get the classical NP-complete problem 3SAT.