Half-SAT/ Half-Satisfiability

First note that your question is not quite right. You asked:

Given … decide whether …

and of course the decision problem is straightforward: just try every possible assignment. I assume that you meant to say “decide in polynomial time”.

---

The Karloff-Zwick algorithm shows that for any instance of 3SAT, there is an assignment that satisfies at least $frac78$ of the clauses.

Karloff-Zwick says: assign the values at random. Then each one of the $n$ causes is satisfied with probability $frac 78$.

By linearity of expectation, the expected number of satisfied clauses $frac78n$.

Since the expected number of satisfied clauses is $frac78n$, then, by the pigeonhole principle, there must be an assignment that satisfies at least $frac78n$ clauses.

So, when $cle frac78$, the problem is not only in $P$, but is trivial, because the answer is always “yes”.

Aaronson (reference below) says “A deterministic polynomial-time algorithm that's guaranteed to satisfy at least $frac78$ of the clauses requires only a little more work.”

---

In contrast, for $c>frac78$, there is probably not any corresponding algorithm, because of this theorem of Håstad:

Suppose there exists a polynomial-time algorithm that, given as input a satisfiable 3-SAT instance, outputs an assignment that satisfies at least a $frac78 +epsilon$ fraction of the clauses, for some positive constant $epsilon$. Then $P=NP$.

This is Håstad, J. 2001 “Some optimal inapproximability results” Journal of the ACM, 48 pp 798–859.

See also Aaronson, Scott “$P{stackrel?=}NP$” p 25.