<p>3-OCC-MAX 2SAT: given a CNF formula $\varphi$ in which each clause contains at most 2 literals and each variable appears in at most three clauses (<em>counting together both positive and negative literals</em>); does there exist an assignment that satisfies at least $k$ clauses?</p>

<p>In <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.8088&amp;rep=rep1&amp;type=pdf" rel="nofollow">P. Berman, M. Karpinski, On some tighter inapproximability results (1998). Lecture
Notes In Computer Science, vol. 1644 (1999), pp. 200-209</a> :</p>

<p>... for any $\epsilon &gt; 0$ it is NP hard to decide whether an
instance of 3-OCC-MAX 2SAT
with $2016 n$ clauses has a truth assignment that satisfies
at least $(2012 - \epsilon)n$ clauses.</p>

<p>As noted in the domotorp's comment, if a variable appers only positive or negative we can fix its value (satisfying and deleting all the clauses in which it appears); so we can assume that the 3 occurrences are not-all-equal ending up in a "3-NAE-OCC-MAX 2SAT" instance :-)  </p>

CC BY-SA 3.0
2014-01-08T21:40:23.940Z
Nice, just what I wanted! Before I accept, why could we not reduce it? If a variable appeared only pos or neg, then we can fix its value, so we can suppose there are no such variables, right?
domotorp
CC BY-SA 3.0
2014-01-08T21:46:28.180Z
@domotorp: you are right :-S ... "3-NAE-OCC MAX 2SAT"! :-) ... I'll edit the answer
Marzio De Biasi
CC BY-SA 3.0
2014-01-12T12:38:57.850Z
I wonder if the problem is also still PLS-complete.
Artem Kaznatcheev
CC BY-SA 3.0
2014-01-08T21:18:02.313Z
2014-01-08T21:50:59.507Z
2014-01-08T21:50:59.507Z
Marzio De Biasi
<p>It is well-known that it is NP-complete to decide whether in a 2-CNF at least s clauses are satisfiable. It also follows from the reduction from 3-SAT-3 that we can suppose that every literal occurs in at most k clauses of the 2-CNF for some constant k. Can someone give me a good bound on k?</p>

<p>Can we suppose that every variable occurs at most twice negated or at most twice unnegated?</p>

<np-hardness><sat><max2sat>
For what k is MAX-2-SAT-k NP-complete?
domotorp
# For what k is MAX-2-SAT-k NP-complete?

(Asked by: username_0 on 2014-01-08)

It is well-known that it is NP-complete to decide whether in a 2-CNF at least s clauses are satisfiable. It also follows from the reduction from 3-SAT-3 that we can suppose that every literal occurs in at most k clauses of the 2-CNF for some constant k. Can someone give me a good bound on k?

Can we suppose that every variable occurs at most twice negated or at most twice unnegated?

**Tags:** np-hardness, sat, max2sat


---

## 1 answers

### Answer by username_1 on 2014-01-08. Score: 6 | Accepted answer

3-OCC-MAX 2SAT: given a CNF formula $\varphi$ in which each clause contains at most 2 literals and each variable appears in at most three clauses (*counting together both positive and negative literals*); does there exist an assignment that satisfies at least $k$ clauses?

In [P. Berman, M. Karpinski, On some tighter inapproximability results (1998). Lecture
Notes In Computer Science, vol. 1644 (1999), pp. 200-209](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.8088&rep=rep1&type=pdf) :

... for any $\epsilon > 0$ it is NP hard to decide whether an
instance of 3-OCC-MAX 2SAT
with $2016 n$ clauses has a truth assignment that satisfies
at least $(2012 - \epsilon)n$ clauses.

As noted in the username_0's comment, if a variable appers only positive or negative we can fix its value (satisfying and deleting all the clauses in which it appears); so we can assume that the 3 occurrences are not-all-equal ending up in a "3-NAE-OCC-MAX 2SAT" instance :-)

> **Comments:**
> **username_0**: Nice, just what I wanted! Before I accept, why could we not reduce it? If a variable appeared only pos or neg, then we can fix its value, so we can suppose there are no such variables, right?  
> **username_1**: @username_0: you are right :-S ... "3-NAE-OCC MAX 2SAT"! :-) ... I'll edit the answer  
> **username_2**: I wonder if the problem is also still PLS-complete.  

---

