7
$\begingroup$

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.

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

2 Answers 2

Reset to default
22
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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) $\endgroup$
    – Suresh Venkat
    Aug 20, 2011 at 17:17
  • $\begingroup$ Hmm, I take it back. Seems that only the optimization version is hard (similar to 2SAT, XOR-SAT, ...). I edited the answer accordingly. $\endgroup$
    – Mahdi Cheraghchi
    Aug 20, 2011 at 17:47
5
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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