Can we make a problem harder than NP and coNP if they are not equal?
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.