Complementing the statement in the post, let us consider the following generalization of HALF-2SAT: for a constant $c$, the language $c$-2SAT consists of all 2SAT instances on $m$ clauses such that some assignment satisfies at least $cm$ clauses. HALF-2SAT is the special case $c = 1/2$.
We have seen above that when $c \leq 1/2$, the answer is always YES. When $c = 1$, this is just 2SAT, which can be solved in polynomial time. Complementing these results, let us show that if $1/2 < c < 1$, the language $c$-2SAT is NP-complete.
Our starting point is the PCP theorem, which states that there is a function $f$ mapping 3SAT instances to 3SAT instances such that:
- If $\phi$ is satisfiable then $f(\phi)$ is satisfiable.
- If $\phi$ is unsatisfiable then at most a $1-\epsilon$ fraction of the clauses of $f(\phi)$ can be simultaneously satisfied.
We compose this with a simple reduction of Garey, Johnson and Stockmeyer, which converts a 3SAT instance $\psi$ to a 2SAT instance $g(\psi)$ by mapping each original clause to 10 new clauses such that:
- For every assignment satisfying an original clause, 7 of the 10 new clauses can be satisfied.
- For every assignment not satisfying an original clause, at most 6 of the 10 new clauses can be satisfied.
Composing the two reductions, we obtain:
- If $\phi$ is satisfiable then a $0.7$ fraction of the clauses of $g(f(\phi))$ can be satisfied.
- If $\phi$ is unsatisfiable then at most a $0.7(1-\epsilon) + 0.6\epsilon = 0.7 - 0.1\epsilon$ fraction of the clauses of $g(f(\phi))$ can be satisfied.
This shows that $0.7$-2SAT is NP-hard. The astute reader will notice that the PCP theorem is not needed for this step – we could just use a direct reduction from 3SAT.
In order to boost this to arbitrary $c$, we either add lots of pairs of clauses of the form $x, \lnot x$ to push $c$ down, or add lots of clauses of the form $x$ to push $c$ up. This is where we use the gap provided by the PCP theorem, for technical reasons.
Let us start with the second case. Suppose that $g(f(\phi))$ contains $m$ clauses. For integers $a,b$, we duplicate $a$ times the formula $g(f(\phi))$, and add $b m$ clauses of the form $x$, where $x$ is a new variable. If $\phi$ is satisfiable, then in the new formula we can satisfy a fraction of $\frac{0.7 a + b}{a+b}$ of the clauses, whereas if $\phi$ is unsatisfiable, we can satisfy at most a fraction of $\frac{(0.7 - 0.1\epsilon)a + b}{a+b}$. We choose $a,b$ so that
$$
\frac{(0.7 - 0.1\epsilon)a + b}{a+b} < c \le \frac{0.7a + b}{a+b}.
$$
To do this, suppose that $c = 0.7 + \delta$. Take $a$ to be large and $b = \lfloor \delta a \rfloor$. The right-hand side tends (as $a\to\infty$) to $c$ (from below) and the left-hand side tends to $0.7-0.1\epsilon+\delta$, so for large enough $a$ the inequality above will be satisfied.
When $c < 0.7$, in addition to adding $bm$ clauses of the form $x$, we also add $bm$ clauses of the form $\lnot x$. Instead of $\frac{0.7a+b}{a+b}$ we now get $\frac{0.7a+b}{a+2b}$; we let the reader complete the proof from here.