So I've been stuck trying to figure this problem out for a while. I've looked on wikis and all over stack exchange but I'm really stumped. This isn't my best subject, so any sort of explanation would be AMAZING.

The Double CNF SAT problem is given a Boolean formula in CNF determine if it
is satisfiable with every clause having at least two literals that are true.
Show that Double CNF SAT is in NP.

I'm really not confident in these SAT, NP problems. I know that NP is the class that consists of problems "verifiable" in polynomial times. So is my goal to show that a double CNF SAT can be verified in polynomial time? If so, how would I do this? How am I supposed to verify it in polynomial time. Is it just a generic solution?

Thanks for any contributions/help

  • $\begingroup$ @D.W. I understand all the definitions... I just don't understand how to show it's in NP, specifically this problem $\endgroup$ – Mark May 6 '15 at 1:34
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your exercise for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. I suggest spending some time to try to do this as best as you can (you might try to review the proof that some other language is in NP and see if you can apply a similar methodology to this problem), and then edit the question to show us your attempt. See here for a relevant discussion. $\endgroup$ – D.W. May 6 '15 at 1:37
  • $\begingroup$ Hint: what are the traditional ways of showing that something is in NP? $\endgroup$ – Ryan May 6 '15 at 1:40
  • $\begingroup$ @D.W. I'm looking for a procedure P such that it runs in polynomial time and can verify the double CNF SAT problem. However, I don't understand how to devise such an algorithm in the context of this problem. I can't just iterate through the clauses and test for each literal can I? $\endgroup$ – Mark May 6 '15 at 1:40
  • $\begingroup$ @Ryan I know I have to construct a deterministic algorithm that decides the language in polynomial time, however I am stuck to devising such an algorithm in the context of this problem $\endgroup$ – Mark May 6 '15 at 1:42

In answer to your comment; yes, you can simply iterate through the clauses. If I had given you a certificate like $$ (y\lor w\lor u)\land(x\lor y\lor \overline{u}\lor z); x=T, y=T, z=F, w=T, u=F $$ could you quickly (in time polynomial in the length of the certificate) verify that (1) the CNF expression is satisfied by the assignments and (2) every clause has at least two literals that are true? Bet you could and could see that this verification is always possible. From that, one can conclude that DOUBLE CNF SAT is indeed in NP.

  • $\begingroup$ I don't think they values of the literals (T | F) are given though. Would that change the answer? I'm pretty sure it would still be in polynomial time since you would just have to check each value of the literal. $\endgroup$ – Mark May 6 '15 at 1:51
  • 2
    $\begingroup$ @Mark. You might be confusing finding a solution with verifying a given possible solution. For a problem to be in NP, all that's required is to check that a proposed solution is correct or not. If the values of the literals were not specified, then you'd basically have to find ones that worked and that could take time exponential in the number of variables. $\endgroup$ – Rick Decker May 6 '15 at 2:02

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