I've been reading lately about SAT problem, NP and co-NP.

Many sources say that the SAT problem is co NP, though, I can't find a co-NP problem equivalent to SAT.

Does anyone have any idea about this ? (Or could lighten my misunderstandings)

  • 1
    $\begingroup$ I'm sure you must have misunderstood those sources. As Yuval Filmus says in his answer, SAT being in co-NP would solve major open problems in complexity theory in the opposite direction to what most researchers expect. So it seems unlikely that there really are "many sources" (at least, not good ones) that say that SAT is in co-NP. $\endgroup$ – David Richerby Oct 24 '14 at 15:50

If SAT is in coNP then NP=coNP, which is believed to be false. However, coSAT, the language of unsatisfiable CNFs, is coNP-complete.

  • 3
    $\begingroup$ And note that co-SAT is not thought of as "equivalent to SAT", in the sense that most complexity theorists believe that they are inequivalent: i.e., they have different complexity. Rather, co-SAT is the co-NP problem that is most naturally paired with SAT when comparing NP and co-NP. $\endgroup$ – David Richerby Oct 24 '14 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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