World's most popular travel blog for travel bloggers.

[Answers] Variation of MAX 3-SAT

, , No Comments
Problem Detail: 

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.

Asked By : fisherinformation

Answered By : Ricky Demer

(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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback