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$
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)$?

$\endgroup$
  • 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 Jun 15 '13 at 6:34

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.