Re: NP problem and co-NP problem
- From: Zhu Guohun <ccghzhu@xxxxxxxxxxxxxxxxxxxx>
- Date: Mon, 14 Jul 2008 07:07:23 -0700 (PDT)
On 7月14日, 上午3时12分, sanchopanch...@xxxxxx wrote:
On 13 Jul., 20:34, sanchopanch...@xxxxxx wrote:
On 13 Jul., 16:59, Zhu Guohun <ccgh...@xxxxxxxxxxxxxxxxxxxx> wrote:
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.
Yes, that is what I meant. Why does it follow?
Thanks,
S.
I am sorry for being so quick. This hasn't been what I meant.
My problem is to prove the two statements:
* Let L be NP-complete and L in co-NP then NP=co-NP
* Let L be NP-complete and cL in NP then NP=co-NP
These are two good questions ( it take me near half hour to thinking
and looking some references)
The first statements is hold
Since L is NPC and L\in co-NP , then NP \subset coNP (1)
for all X in co-NP , then cX in NP , according to
(1) cX is in coNP again , then X in NP coNP \subset NP
thus NP=co-NP
The second statements is holds
Since L is NPC , cL is in NP L is in co-NP then NP
\subset coNP (2)
for all X in co-NP, then cX in NP , according to (2)
cX is in coNP, X is NP, coNP \subset NP
-----------------------------------------
Zhu
Thanks,
Sancho- 隐藏被引用文字 -
- 显示引用的文字 -
.
- References:
- NP problem and co-NP problem
- From: sanchopancho80
- Re: NP problem and co-NP problem
- From: Zhu Guohun
- Re: NP problem and co-NP problem
- From: sanchopancho80
- Re: NP problem and co-NP problem
- From: sanchopancho80
- NP problem and co-NP problem
- Prev by Date: Re: Rice's theorem
- Next by Date: reducing the factorization decision problem to SAT?
- Previous by thread: Re: NP problem and co-NP problem
- Next by thread: Is this language context free?
- Index(es):
Relevant Pages
|
