Take a graph G and integer k that is an instance of the IS
From these construct a graph G' formed from G by
complementing the set of edges.
That is, there is an edge (x,y) in G' if and only if there
is not an edge (x,y) in G.
The pair consisting of G' and the integer k is an instance
In proof, if G has an independent set of size k, then
there are no edges among these nodes in G.
Thus, all the edges among these nodes are in G', where they form
a clique of size k.
Conversely, if G' has a clique of size k, then in G
there are no edges among these nodes, so they are an independent set in
The key point is that if P reduces to Q, then the
-P (we use - for ``complement of'')
reduces to -Q by the same
Suppose Q is an NP-complete problem that is in co-NP.
Then every problem P in NP is in co-NP; just transform -P
to -Q in polynomial time and then use the nondeterministic
polynomial-time algorithm for -Q to solve -P in
nondeterministic polynomial time.
Thus, P is in co-NP.
That shows NP is contained in co-NP.
For the other half of the equality NP = co-NP, suppose P is in
That is, -P has a nondeterministic polynomial-time algorithm.
Since Q is NP-complete, there is a polynomial-time reduction of
-P to Q, and thus, such a reduction from P to
Since Q is in co-NP, -Q is in NP, and thus so is
That shows co-NP is contained in NP, and we now have NP = co-NP.