Re: NP vs co-NP

On Jul 13, 5:00 am, sanchopanch...@xxxxxx wrote:
Hello,

why is it true that NP = co-NP if there is an NP-complete language L
whose complement is in NP, too?

My textbook argues as follows (cL denotes the complement of L):
Because every NP language S is polynomial-time reducible to L, i.e.
S<L if follows that cS is polynomial-time reducible to cL, i.e.
cS<cL...
I don't understand this up to here. Why does cS<cL follow? Could
anybody help me?

Another question is what happens if there is an NP-complete language L
which is is co-NP, too. Does it follow that co-NP=NP?

Thanks,
S.

I am fairly sure that there is no co-NP-complete language that is
known to be in NP. If you are referring to the language TAUTOLOGY,
that is NP-hard, not NP-complete. To be NP-complete, a language must
be in NP, meaning there must be a certificate of reasonable length for
membership in the language. Yes, SAT is reducible to TAUTOLOGY; but
TAUTOLOGY is not in NP, so it's not considered NP-complete.

I'm not sure if an NP-complete language being in co-NP implies that NP
= co-NP, but my suspicion is that it would. However, I don't know how
to prove it, so I might be wrong.

-Phil
.

Quantcast