5
$\begingroup$

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.

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

Yes, your argument is correct.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.