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

Question

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}$.

Answer 1

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.

Answer 2

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.