1
$\begingroup$

Is it true that if SAT is in coNP then its also coNP-complete (because it is NP-complete)?

$\endgroup$
4
$\begingroup$

If SAT is in coNP then since coSAT is coNP-complete, SAT can be reduced to coSAT in polytime. The same reduction also reduces coSAT to SAT. Since coSAT is coNP-complete, every problem in coNP can be reduced in polytime to coSAT, and so to SAT. This shows that SAT is coNP-complete.

$\endgroup$

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.