Re: NP problem and co-NP problem

On 7月13日, 下午10时20分, sanchopanch...@xxxxxx wrote:
Hello,

please let me post my last question again because the old name seems
to make problems with other threads.

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?


Not correctly ( I don't know what is your textbook)
S<L can only follows cL < cS.

------------------
Zhu

.

Relevant Pages

  • NP problem and co-NP problem
    ... Why is it true that NP = co-NP if there is an NP-complete language L ... My textbook argues as follows (cL denotes the complement of L): ... Another question is what happens if there is an NP-complete language L ...
    (comp.theory)
  • NP vs co-NP
    ... My textbook argues as follows (cL denotes the complement of L): ... Another question is what happens if there is an NP-complete language L ... which is is co-NP, too. ...
    (comp.theory)
  • Re: NP vs co-NP
    ... My textbook argues as follows (cL denotes the complement of L): ... Because every NP language S is polynomial-time reducible to L, ... Another question is what happens if there is an NP-complete language L ... which is is co-NP, too. ...
    (comp.theory)