Complexity of specific cases of MAX2SAT

Question

I know that MAX2SAT is NP-complete in general but I'm wondering about if certain restricted cases are known to be in P. Certainly the languages

$L_k:=\{ \phi \,|\, \phi\,\text{is an instance of 2SAT which has an assignment satisfying at least k clauses.}\}$

can be solved in $O(n^k)$ through brute force search since for each language $k$ is fixed. However, I'm wondering about the case when a fraction of the clauses is specified. Does any fraction yield an NP-hard problem? Specifically I'm wondering about the case of satisfying at least half of the clauses of a 2SAT instance.

The reduction I saw from 3SAT to MAX2SAT constructs 10 clauses from each clause in 3SAT such that out of these ten, exactly 7 are satisfied when the original 3SAT clause is satisfied and at most 6 are satisfied when the original clause is not satisfied. So in this reduction the fraction of $7/10$ works but $1/2$ does not because unsatisfying truth assignments of a 3SAT instance can still yield an instance of 2SAT that has an assignment satisfying more than half of the clauses. I thought about another construction or adding extra clauses to an instance of 2SAT but I've been unsuccessful so far.

Answer 1

You can always satisfy at least half of clauses: for each variable $x$, find the number of clauses that contain $x$ and the number of clauses that contain $\lnot x$. Select the one which satisfies the most clauses. Remove clauses containing $x$ and $\lnot x$. Repeat for other variables.

Since for each $x$ we satisfy at least half of removed clauses, we satisfy half of the clauses overall.

On the other hand, it's also tight: let $\alpha > \frac 12$ be the fraction of clauses for which we can give an answer. Let $\beta > \frac 12$ be the maximum fraction of clauses we can satisfy in a specific clause. Then we can add clauses so that $\beta$ (for the new clause) becomes arbitrary clause to $\alpha$:

• If $\beta < \alpha$, then we can add clauses $(x_i \lor \lnot x_i)$, until $\beta > \alpha$ (since these clauses are always true, $\beta$ increases).
• If $\beta > \alpha$, we can add clauses $(x_i)$ and $(\lnot x_i)$, until $\beta < \alpha$ (since exactly half of clauses is true, $\beta$ decreases).

I didn't check, but to get $O(\frac 1m)$ difference (i.e. to find the exact number of clauses), I think it suffices to add $O(m)$ clauses. In other words, if we can solve for some $\alpha > \frac 12$, we can check for any $\beta$ whether $\beta$ fraction of clauses can be satisfied, and therefore we can solve MAX2SAT in polynomial time.