2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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) $\endgroup$ – Ari Aug 10 at 0:57
  • $\begingroup$ 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?" $\endgroup$ – Eric Towers Aug 10 at 5:10
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.