Skip to main content
1 of 4

A question about assuming Co-NP != NP

Let us assume that NP $\neq$ Co-NP, and let's focus on the graph 3-colorability problem.

Since NP $\neq$ Co-NP:

  1. There is no algorithm that can recognize any 3-colorable graph in polynomial time.
  2. There are no polynomial certificates in general for certifying non-3-colorability.

However, we know that for many classes of graphs, polynomial algorithms exists and also polynomial certificates for certifying non-3-colorability.

So, given a graph $G$, deciding 3-colorability is NP-complete and non-3-colorability is Co-NP-complete.

Since we assumed that NP $\neq$ Co-NP then we have another problem:

Given a graph $G$: is there an algorithm, bounded by a polynomial of order $k$, that can determine if $G$ is 3-colorable-or-non-3-colorable and provide a certificate?

The certificate is either a 3-coloring or a non-3-colorability certificate, so YES version is in NP. And the NO version is in Co-NP. Note that the answer is not alway yes since NP $\neq$ Co-NP.

And so we can define a third order problem of deciding if the second order problem has polynomial solution or not.

We can continue this process infinitely...

In general, for every YES (NP) problem the certificates are defined by the union of all the possible certificates that can be generated for each previous problem, however since $G$ is finite and the certificate should be bounded by a polynomial in $k$ then some problem will have as a certificate all possible certifying strings, that is, every input will be recognized as YES so the NP problem of the immediate upper level will be also solvable in P, and so on. And this will contradict the assumption that NP $\neq$ Co-NP.

Are there any steps in which we can stop this infinite problem loop? Is there any easy explanation for this in some place? Have this a silly mistake?