# Complexity of specific cases of MAX2SAT

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.

• @D.W. My apologies it's a typo. I'll fix it. Yet I'd also be interested if the same idea applies to MAX3SAT (i.e. if the fractional case be NP hard) – Ari Aug 10 '20 at 0:57
• You might read cs.cmu.edu/~avrim/Randalgs11/lectures/avrim-maxsat.pdf , which suggests that the right framing is as a fraction of the MAX2SAT fraction of the problem instance -- i.e., "for this problem instance, what is the time complexity of finding a variable assignment that satisfies $73/74$ of the maximum number of simultaneously satisfiable clauses?" – Eric Towers Aug 10 '20 at 5:10

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.