# Can we make a problem harder than NP and coNP if they are not equal?

Let us assume that $\mathsf{NP} \neq \mathsf{coNP}$. Consider the graph 3-colorability problem.

Since $\mathsf{NP} \neq \mathsf{coNP}$ implies $\mathsf{P} \neq \mathsf{NP}$ and 3-coloribility is $\mathsf{NP}$-complete and its complement is $\mathsf{coNP}$-complete , we have:

1. 3-coloribility is not in $\mathsf{P}$, i.e. there are no polynomial-time algorithm for deciding if a given graph is 3-colorable.
2. non-3-coloribility is not in $\mathsf{NP}$, i.e. there are no polynomial-time verifier with polynomial-size certificatesfor non-3-colorability.

However, we know that for many classes of graphs, polynomial algorithms exists for 3-colorability and also they have polynomial-time verifiers with polynomial-size certificates for non-3-colorability. But this is not the case for all graphs since we we assumed that $\mathsf{NP} \neq \mathsf{coNP}$.

We can define the following problem:

Input: a graph $G$,
Task: determine if $G$ is 3-colorable or non-3-colorable and provide a certificate for the answer. The certificate is either a 3-coloring or a non-3-colorability certificate.

What is the complexity of this problem?

YES version is in $\mathsf{NP}$ . And the NO version is in $\mathsf{coNP}$. Note that the answer is not always YES since $\mathsf{NP} \neq \mathsf{coNP}$.

• Talking about an algorithm for a specific instance does not make sense in computational complexity theory. Feb 13, 2013 at 0:22
• Thanks, but I don't understand why you say that I am dealing with a specific instance. Could you please explain? Feb 13, 2013 at 0:31
• The following problem does not make sense: “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?” Feb 13, 2013 at 0:42
• I can't make much sense of the later part of the post. It looks to me like ideas for/a naive attempt to solve NP vs. coNP which doesn't work (not for any deep reason but for trivial reasons). If that is the case and that was the main intention behind the post, IMHO, it might be better to first learn basics of complexity theory and solve some problems of average difficulty before trying to solve famous problems which have been open for a few decades. Feb 13, 2013 at 5:07
• A more reasonable way of doing this might be considering the following problem: given a graph $G$ and a bit $b$, answer YES if $G$ is 3-colorable and $b=1$, or $G$ is not 3-colorable and $b=0$. Then the problem is hard for both NP and coNP (under Karp reductions) so it doesn't belong to either. Feb 15, 2013 at 16:26

Note: this answer was posted for the original post.

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?

If you fix the graph then the problem is trivial. There is always an algorithm that answers in constant time. There is no input.

If the graph is the input, then the answer is always YES. Any graph is either 3-colorable or not 3-colorable.

Note that the answer is not alway yes since NP ≠ Co-NP

I don't see how this is relevant.

• I think by "determine if G is 3-colorable-or-non-3-colorable" the OP means can return a boolean TRUE if the graph is 3-colorable and FALSE if the graph is not. Feb 13, 2013 at 6:36
• @jmite, no, that is just the 3-coloring problem: decide if a given graph is 3-colorable or not? Feb 13, 2013 at 7:42
• Graph G is the input plus an integer k. Will your algorithm provide either a 3-coloring of G or a 3-uncolorability certificate in j<=k basic operations? Feb 13, 2013 at 13:21
• @Jose, no, it doesn't, but 1. that is not a decision problem, 2. you haven't asked for that. If that is what you want please edit your post and clearly and rigorously state your problem: what is the input and what is the output and then ask about the complexity of solving that problem. Also including $k$ in the input doesn't make much sense. Feb 13, 2013 at 20:43
• ps: IMHO you should also remove the later part of your post (from "And so we can define..."). Feb 13, 2013 at 20:46

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?

I think what you meant here was: given a graph $G$, find whether there is a certificate or short proof for whether it is 3-colorable. What you're missing here is that there is no optimal polynomial time algorithm that finds such certificates, if possible. You can always extend a given "optimal" algorithm by hardwiring the answer to a finite number of graphs.

Moreover, for any graph $G$ there is an algorithm that outputs YES, NO, or DON'T KNOW, never makes a mistake, and is correct on $G$. It's even linear time [edit: actually constant time]. Furthermore, the algorithm is provably correct.

• Moreover, for any graph G there is an algorithm that outputs YES, NO, or DON'T KNOW, never makes a mistake, and is correct on G. It's even linear time. Furthermore, the algorithm is provably correct.? What? Which algorithm is it? Feb 14, 2013 at 23:29
• It's a nice riddle, I don't want to spoil it for you. Feb 15, 2013 at 3:59
• Yes of course the trivial ones, but whats the probability of each case? If almost all graphs receive a DON'T KNOW it is non-useful. Feb 15, 2013 at 10:04
• Linear time? Don't you mean constant time?! Feb 15, 2013 at 16:38
• You're right Jeff! I though it would take linear time to compare the input to $G$, but that's actually constant. Feb 16, 2013 at 6:14