Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
15  
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
5  
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
6  
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
show 2 more comments

2 Answers 2

up vote 21 down vote accepted

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.

share|improve this answer
1  
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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