# Is the following langauge in $P$ or $NPC$

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 ?

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)$?
• 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. – Luke Mathieson Jun 15 '13 at 6:34