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