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)
$\begingroup$
$\endgroup$
-
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
$\begingroup$
$\endgroup$
If SAT is in coNP then NP=coNP, which is believed to be false. However, coSAT, the language of unsatisfiable CNFs, is coNP-complete.
answered Oct 24 '14 at 15:38
-
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
