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

-

migrated from cstheory.stackexchange.comFeb 13 '13 at 3:58

This question came from our site for theoretical computer scientists and researchers in related fields.

Talking about an algorithm for a specific instance does not make sense in computational complexity theory. –  Tsuyoshi Ito Feb 13 '13 at 0:22
Thanks, but I don't understand why you say that I am dealing with a specific instance. Could you please explain? –  Jose Antonio Martin H Feb 13 '13 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?” –  Tsuyoshi Ito Feb 13 '13 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. –  Kaveh Feb 13 '13 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. –  Kaveh Feb 15 '13 at 16:26

2 Answers

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. –  jmite Feb 13 '13 at 6:36
@jmite, no, that is just the 3-coloring problem: decide if a given graph is 3-colorable or not? –  Kaveh Feb 13 '13 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? –  Jose Antonio Martin H Feb 13 '13 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. –  Kaveh Feb 13 '13 at 20:43
ps: IMHO you should also remove the later part of your post (from "And so we can define..."). –  Kaveh Feb 13 '13 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? –  Jose Antonio Martin H Feb 14 '13 at 23:29
It's a nice riddle, I don't want to spoil it for you. –  Yuval Filmus Feb 15 '13 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. –  Jose Antonio Martin H Feb 15 '13 at 10:04
Linear time? Don't you mean constant time?! –  JeffE Feb 15 '13 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. –  Yuval Filmus Feb 16 '13 at 6:14