2
$\begingroup$

Assuming $P \neq NP$ Is the following langauge in $P$ or $NPC$:
$L=\{\langle\phi\rangle\mid\phi$ is a 3CNF formula with an assignment satisfying at least half of the clauses$\}$

The first thing I tried to do is to find a 3CNF formula $\phi$ such that $\phi \notin L$ and I haven't managed to do so. Is it possible that simply all 3CNF formulas have such an assignment (and so the problem is in $P$) or am I missing something ?

$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Hint: Take a valuation $v$ satisfying less than half of the clauses. What about $\bar{v}$ the valuation such that $\bar{v}(x)=\neg v(x)$?

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Just as a little side note, if each clause has exactly 3 literals (some might allow 3CNF to mean at most 3), then you can expect to satisfy $\frac{7}{8}$ of the maximum number of simultaneously satisfiable clauses. A proof of this here. $\endgroup$
    – Luke Mathieson
    Commented Jun 15, 2013 at 6:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.