Monday, November 8, 2010

Show that L is complete for NP if and only if L-complement is complete for co-NP

Today I attempt to solve the following problem:


Show that, with respect to polynomial-time reductions, L is complete for NP if and only if L-complement is complete for co-NP.
-------------------------------------------------------


SOLUTION:
Let's start by remembering that:
co-NP is the set of languages L such that L-comp ∈ NP


and remember that
A language L is complete for NP if both, ∈NP and L is NP-Hard (meaning that for every language L' NP there is a polynomial-time reduction p such that L' p L, namely L' can be reduced to L in polynomial-time).


In notation: ∈ NPC iff L∈NP && L' p L,∀ L'∈ NP
--------------------------------------------------------------------


First we show that ∈ NPC then L-comp ∈ co-NPC:


See that if ∈ NPC then L ∈ NP //by definition of NPC
and if ∈ NP then L-comp ∈ co-NP because L-comp-comp = ∈ NP
                              // by def of co-NP


So right now we've proved half of one side. We've proved that if:
if ∈ NPC then L-comp ∈ co-NP.
The harder part now is to prove that:
if ∈ NPC then  L' p L-comp,L'∈ co-NP


Observe that 
L'-comp ∈ co-NP, L'∈ NP //by def of co-NP
Then it is easy to derive that for ∈ NPC
if L' p L,L'∈ NP then  L'-comp p L,L'∈ co-NP


Now all we need to prove is that
 if L'-comp p L then L' p L-comp, which is easy.


L'-comp p L means that L'-comp is polynomial-time reducible to L
Let f(x) : {0,1}* --> {0,1}* be the polynomial-time computable function that we 
can use to reduce L'-comp to L


Then for f(x) we know the following: ∈ L'-comp iff f(x)∈ L, ∀x∈ {0,1}*
and hence  L'-comp iff f(x)  L ∀x∈ {0,1}*
and so: ∈ L' iff f(x)∈ L-comp, ∀x∈ {0,1}*
which means that we can use the same function f(x) that reduces L'-comp to L to 
reduce L' to L-comp.
That means that L' p L-comp
So we've proved that if ∈ NPC then L-comp ∈ co-NP
and that if ∈ NPC then  L' p L-comp,L'∈ co-NP
which means that we proved that 
if ∈ NPC then L-comp ∈ co-NPC.
The proof in the other direction is analogous to this one, 
and I am not going to write it down.


Q.E.D?

No comments:

Post a Comment