patternMinor
Isn't this language in $\mathrm{P}^{\mathrm{NP}}$?
Viewed 0 times
thisisnmathrmlanguage
Problem
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.
$$
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.
Solution
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.
$\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.
Context
StackExchange Computer Science Q#104634, answer score: 4
Revisions (0)
No revisions yet.