<p>This problem is sometimes called CSP(Maj), and is a constraint satisfaction problem where each constraint is a Majority predicate on 3 variables. The problem is in P, as a special case of the following result:</p>

<p>T. Schaefer. The complexity of satisability problems. In Conference record of the Tenth
annual ACM Symposium on Theory of Computing, pages 216--226, 1978.</p>

<p>However, PCP theory shows that the optimization version of the problem Max-CSP(Maj) is inapproximable within some constant factor.</p>

CC BY-SA 3.0
2011-08-20T16:45:59.183Z
2011-08-20T17:45:14.667Z
2011-08-20T17:45:14.667Z
Mahdi Cheraghchi
<p>At least two of the literals $x$, $y$, $z$ are satisfied iff at least one literal in each pair $(x,y)$, $(x,z)$, $(y,z)$ is satisfied. Therefore it is a special case of <a href="http://en.wikipedia.org/wiki/2-satisfiability">2SAT</a>, and there is a polynomial-time algorithm for solving it.</p>

CC BY-SA 3.0
2011-08-20T17:17:07.947Z
Jukka's statement is correct however. The IFF does indeed hold. Specifically, his argument would seem to place this in category 3 of Schaeffer's theorem (link above)
Suresh Venkat
CC BY-SA 3.0
2011-08-20T17:47:15.927Z
Hmm, I take it back. Seems that only the optimization version is hard (similar to 2SAT, XOR-SAT, ...). I edited the answer accordingly.
Mahdi Cheraghchi
CC BY-SA 3.0
2011-08-20T09:03:03.623Z
2011-08-20T09:03:03.623Z
Jukka Suomela
<p>I have the following problem:</p>

<pre><code>We are given an instance of the 3-SAT problem.
Is there a satisfying assignment s.t. at least two literals are satisfied in each clause?
</code></pre>

<p>The question is:</p>

<pre><code>Is the problem NP-complete?
</code></pre>

<p>The question might sound stupid, but I couldn't figure it out by myself.</p>

<p>I searched the web and in books but didn't find anything.</p>

<p>I also tried to reduce 3-SAT to it, but without success.</p>

<p>(I have to admit that I didn't spent much time to do it since it is not my main research focus; this is just a question that came to my mind while working on another problem. I am interested in the answer because if it turns out to be NP-complete it could help me in a future problem.)</p>

<p>Thanks in advance for your answers! Every answer or comment is welcome.</p>

CC BY-SA 3.0
2011-08-20T00:21:59.957Z
It is a special case of 2SAT. At least two of the literals $x$, $y$, $z$ are satisfied iff at least one literal in each pair $(x,y)$, $(x,z)$, $(y,z)$ is satisfied.
Jukka Suomela
CC BY-SA 3.0
2011-08-20T01:34:01.067Z
@Jukka you should make that as an answer, unless this question is deemed non-research level by the moderators (it seems dangerously close to it).
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-20T01:52:35.760Z
A good, general theorem to know about for variants on SAT: http://en.wikipedia.org/wiki/Schaefer%27s_dichotomy_theorem
Daniel Apon
CC BY-SA 3.0
2011-08-20T02:03:37.900Z
@Jukka Suomela Thanks for your help! I knew something is wrong with this :) It's obvious now.
George
CC BY-SA 3.0
2011-08-20T02:03:51.987Z
@Artem Kaznatcheev It probably is close to it. I got my answer now, so I can delete it or vote to close it.
George
CC BY-SA 3.0
2011-08-20T05:41:11.023Z
At this point, a better solution would be that Jukka posts the comment as an answer and George B accepts it
Suresh Venkat
<cc.complexity-theory><sat>
Not-one 3-SAT; How hard is it?
George
# Not-one 3-SAT; How hard is it?

(Asked by: username_0 on 2011-08-20)

I have the following problem:
We are given an instance of the 3-SAT problem.
Is there a satisfying assignment s.t. at least two literals are satisfied in each clause?

The question is:
Is the problem NP-complete?

The question might sound stupid, but I couldn't figure it out by myself.
I searched the web and in books but didn't find anything.
I also tried to reduce 3-SAT to it, but without success.
(I have to admit that I didn't spent much time to do it since it is not my main research focus; this is just a question that came to my mind while working on another problem. I am interested in the answer because if it turns out to be NP-complete it could help me in a future problem.)
Thanks in advance for your answers! Every answer or comment is welcome.

**Tags:** cc.complexity-theory, sat

> **Comments:**
> **username_1**: It is a special case of 2SAT. At least two of the literals $x$, $y$, $z$ are satisfied iff at least one literal in each pair $(x,y)$, $(x,z)$, $(y,z)$ is satisfied.  
> **username_2**: @Jukka you should make that as an answer, unless this question is deemed non-research level by the moderators (it seems dangerously close to it).  
> **username_3**: A good, general theorem to know about for variants on SAT: http://en.wikipedia.org/wiki/Schaefer%27s_dichotomy_theorem  
> **username_0**: @username_1 Thanks for your help! I knew something is wrong with this :) It's obvious now.  
> **username_0**: @username_2 It probably is close to it. I got my answer now, so I can delete it or vote to close it.  
> **username_4**: At this point, a better solution would be that Jukka posts the comment as an answer and username_0 B accepts it  

---

## 2 answers

### Answer by username_1 on 2011-08-20. Score: 22 | Accepted answer

At least two of the literals $x$, $y$, $z$ are satisfied iff at least one literal in each pair $(x,y)$, $(x,z)$, $(y,z)$ is satisfied. Therefore it is a special case of [2SAT](http://en.wikipedia.org/wiki/2-satisfiability), and there is a polynomial-time algorithm for solving it.

> **Comments:**
> **username_4**: Jukka's statement is correct however. The IFF does indeed hold. Specifically, his argument would seem to place this in category 3 of Schaeffer's theorem (link above)  
> **username_5**: Hmm, I take it back. Seems that only the optimization version is hard (similar to 2SAT, XOR-SAT, ...). I edited the answer accordingly.  

---

### Answer by username_5 on 2011-08-20. Score: 5

This problem is sometimes called CSP(Maj), and is a constraint satisfaction problem where each constraint is a Majority predicate on 3 variables. The problem is in P, as a special case of the following result:

T. Schaefer. The complexity of satisability problems. In Conference record of the Tenth
annual ACM Symposium on Theory of Computing, pages 216--226, 1978.

However, PCP theory shows that the optimization version of the problem Max-CSP(Maj) is inapproximable within some constant factor.


---

