1
$\begingroup$

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.

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

(I don't know whether "3CNF" means exactly 3 literals per clause, or
at most 3 literals per clause. ​ I will address the more general case.)

Empty clauses can't be satisfied, so removing them affects
neither the maximum nor which assignments achieve that.
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,
so at least one assignment satisfies at least half of the non-empty clauses.
(One can efficiently-and-deterministically find such an
assignment via the method of conditional expectation.)
Thus, your problem can be kernelized in linear time into less than 2$\cdot$k clauses.

$\endgroup$
2
$\begingroup$

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.

$\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.