Re: NP vs co-NP
- From: Chris Smith <cdsmith@xxxxxxxxx>
- Date: 13 Jul 2008 14:33:29 GMT
sanchopancho80 wrote:
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?
Think about what that means. If S is polynomial-time reducible to L,
then there exists a polynomial-time computable function f on strings,
such that x is in S if and only if f(x) is in L. The normal path is
that you'd then try to decide S by computing f(x) for the input x, and
then calling the decider for L. But the exact same function f suffices
as a polynomial reduction from cS to cL! This is actually obvious; you
just have to take contrapositives, and note that (x is not in S) is the
same statement as (x is in cS).
--
Chris Smith
.
- References:
- NP vs co-NP
- From: sanchopancho80
- NP vs co-NP
- Prev by Date: NP problem and co-NP problem
- Next by Date: Re: NP problem and co-NP problem
- Previous by thread: NP vs co-NP
- Next by thread: Re: NP vs co-NP
- Index(es):
Relevant Pages
|
