# Isn't this language in $\mathrm{P}^{\mathrm{NP}}$?

For an undirected graph $$G$$, let us denote $$\gamma(G)$$ the chromatic number of $$G$$. Let us define for positive integer $$n$$, the language $$L_n = \{\langle G\rangle : \gamma(G) = n\}.$$ This is the language of undirected graphs with chromatic number $$n$$. I think $$L_n \in \mathrm{P}^{\mathrm{NP}}$$, for any $$n$$.

My argument is the following. We can look at the language, $$\mathrm{CHROMNUM} = \{\langle G, k\rangle : \gamma(G) \leq k\}.$$ It is clear that $$\mathrm{CHROMNUM} \in \mathrm{NP}$$, since we can verify an instance just by displaying an at most $$k$$-coloring of $$G$$.

Thus, consider oracle Turing machine $$M^{\mathrm{CHROMNUM}}_n$$, which on input $$G$$, simply checks that $$\langle G, n \rangle \in \mathrm{CHROMNUM}$$ and that $$\langle G, k \rangle \not \in \mathrm{CHROMNUM}$$ for all $$k \leq n$$.

I've just read about $$\mathrm{P}^{\mathrm{NP}}$$, so I wanted to be sure that this kind of argument is correct.

• In fact, you get the same complexity even if $n$ is a parameter. – Yuval Filmus Feb 21 '19 at 9:04

$$\textbf{P}^\textbf{NP}$$ is the class of problems which are Cook-reducible (i.e., polynomial-time Turing-reducible) to $$\textbf{NP}$$. A Turing reduction to $$\textbf{NP}$$ is simply a reduction with oracle access to a problem in $$\textbf{NP}$$, in this case the problem $$\text{CHROMNUM}$$.
In fact, using your reasoning and the fact that $$\langle G, k \rangle \not\in \text{CHROMNUM} \implies \langle G, k' \rangle \not\in \text{CHROMNUM}$$ for all $$k' \le k$$, you can prove that you only need two oracle queries (independent of $$n$$). That is, your reduction resumes to checking the following: $$\langle G, n \rangle \in \text{CHROMNUM} \land \langle G, n - 1 \rangle \not\in \text{CHROMNUM}$$ This means you only need one $$\textbf{NP}$$ query and one $$\textbf{coNP}$$ query (since checking if something is not in an $$\textbf{NP}$$ language is in $$\textbf{coNP}$$). As it turns out, there is a class of problems which are characterized by having the same type of reduction, the difference polynomial time class $$\textbf{D}^\textbf{P}$$, and which, incidentally, coincides with the second level of the Boolean hierarchy.