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, L ∈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: L ∈ NPC iff L∈NP && L' ≤p L,∀ L'∈ NP
--------------------------------------------------------------------
First we show that L ∈ NPC then L-comp ∈ co-NPC:
See that if L ∈ NPC then L ∈ NP //by definition of NPC
and if L ∈ NP then L-comp ∈ co-NP because L-comp-comp = L ∈ NP
// by def of co-NP
So right now we've proved half of one side. We've proved that if:
if L ∈ NPC then L-comp ∈ co-NP.
The harder part now is to prove that:
if L ∈ 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 L ∈ 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: x ∈ L'-comp iff f(x)∈ L, ∀x∈ {0,1}*
and hence x ∉ L'-comp iff f(x) ∉ L ∀x∈ {0,1}*
and so: x ∈ 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 L ∈ NPC then L-comp ∈ co-NP
and that if L ∈ NPC then L' ≤p L-comp,∀L'∈ co-NP
which means that we proved that
if L ∈ 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