Consider to following decision problem:
Input: Undirected graph $G=(V,E)$
Question: Is the minimum numbers of colors needed to color the vertices (such that every two adjacent vertices aren't colored the same) exactly 2015?
Note that 2015 could be any fixed number. This number is not part of the input.
I need to understand what is the minimal complexity class that contain this problem, between $\sf P,NP,coNP,NP\cup coNP,\Sigma _{2} \cap \Pi _{2}, \Sigma _{2} \cup \Pi _{2}$.
I don't it's $\sf NP$ or $\sf coNP$ since I can't think of a verifier for both the language or it's complement. The problem is maybe in $\sf \Sigma _{2} \cap \Pi {2}$ since we can think of it as
exists $f$ some 2009-coloring function, for-all $g$, 2008-coloring function, $f$ is a correct coloring and $g$ isn't a correct coloring.
So by the above, it seems that the language is in $\sf \Sigma _{2}$, but the quantifiers order doesn't really matter here, so the language is also in $\sf \Pi _{2}$, I think.
And maybe the there is some deterministic polynomial-time algorithm?