- 3-coloribility is not in $mathsf{P}$, i.e. there are no polynomial-time algorithm for deciding if a given graph is 3-colorable.
- 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}$.
Asked By : Jose Antonio Martin H
Answered By : Kaveh
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9734
