# Not-one 3-SAT; How hard is it?

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.)

-
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 Aug 20 '11 at 0:21
@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 Aug 20 '11 at 1:34
A good, general theorem to know about for variants on SAT: en.wikipedia.org/wiki/Schaefer%27s_dichotomy_theorem –  Daniel Apon Aug 20 '11 at 1:52
@Jukka Suomela Thanks for your help! I knew something is wrong with this :) It's obvious now. –  George Aug 20 '11 at 2:03
At this point, a better solution would be that Jukka posts the comment as an answer and George B accepts it –  Suresh Venkat Aug 20 '11 at 5:41

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, and there is a polynomial-time algorithm for solving it.

-
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 Aug 20 '11 at 17:17
Hmm, I take it back. Seems that only the optimization version is hard (similar to 2SAT, XOR-SAT, ...). I edited the answer accordingly. –  MCH Aug 20 '11 at 17:47

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.

-