<p>[Summarizing the answers in the comments by Ricky Demer and Josh Grochow.]</p>

<p>$\mathsf{NP}^{\mathsf{GI}} = \mathsf{NP}^{GraphIso}$, since these are nondeterministic poly-time <em>Turing</em> reductions, which can be simulated by the oracle machine (as detailed e.g. <a href="https://cs.stackexchange.com/questions/26317/question-about-the-definition-of-complexity-class-oracles/26332#26332">here</a>). </p>

<p>The bounded-time halting problem for non-deterministic machines with a GraphIso oracle is complete for this class, by the usual proof.</p>

<p>Under standard derandomization assumptions (in particular, any that imply $\mathsf{AM} = \mathsf{NP}$), $\mathsf{NP}^{\mathsf{GI}} = \mathsf{NP}$, since under such assumption we have $\mathsf{GI} \subseteq \mathsf{NP} \cap \mathsf{coNP}$, and the latter is low for $\mathsf{NP}$.</p>

CC BY-SA 3.0
2015-12-16T06:13:51.750Z
2015-12-16T06:13:51.750Z
2017-04-13T12:48:30.830Z
Joshua Grochow
<p><strong>Definition</strong>: Let $GraphIso$ be the decision problem whose input is a pair of undirected graphs $(G_1, G_2)$ and the output is <strong>true</strong> if and only if $G_1$ and $G_2$ are isomorphic.</p>

<p><strong>Definition</strong>: Define $\textbf{GI}$ to be the class of all decision problems $L$ for which there is a polynomial-time Turing reduction from $L$ to $GraphIso$.</p>

<p><strong>Definition</strong>: Let $\textbf{NP}^{\textbf{GI}}$ be the class all decision problems which can be decided by a polynomial-time non-deterministic Turing machine with access to an oracle for a problem which is in $\textbf{GI}$.</p>

<p>My question is then: is this class known? Is it equivalent to a more standard complexity class? Is there any know complete problem for this class?</p>

CC BY-SA 3.0
2015-10-20T20:38:59.650Z
It's interesting though that for $GI$, a problem $L$ is said to be $GI$-complete if and only if (1) $L$ is in $GI$ (i.e. there is a polynomial-time Turing reduction from $L$ to $GraphIso$) and (2) $L$ is $GI$-hard, which by definition means that there is a polinomial-time Turing reduction (not many-to-one reduction!) from $GraphIso$ to $L$. The more relaxed reductions used make this slightly different than what I would call a normal "nice" syntactic class...
gdiazc
CC BY-SA 3.0
2015-10-20T21:05:13.437Z
I agree with this, but what about a natural $NP^{GI}$-complete problem?
gdiazc
CC BY-SA 3.0
2015-10-21T02:48:27.373Z
@gdiazc: The bounded-time halting problem for nondeterministic machines with a GraphIso oracle should be complete for this class. Also, note that under a standard derandomization assumption (namely, $\mathsf{NP} = \mathsf{AM}$), we would have $\mathsf{NP}^{GI} = \mathsf{NP}$, since in this scenario GI would be in $\mathsf{NP} \cap \mathsf{coNP}$, which is low for $\mathsf{NP}$.
Joshua Grochow
<cc.complexity-theory><graph-isomorphism>
Complete problems or alternative definitions of the complexity class NP^GI?
gdiazc
# Complete problems or alternative definitions of the complexity class NP^GI?

(Asked by: username_0 on 2015-10-20)

**Definition**: Let $GraphIso$ be the decision problem whose input is a pair of undirected graphs $(G\_1, G\_2)$ and the output is **true** if and only if $G\_1$ and $G\_2$ are isomorphic.

**Definition**: Define $\textbf{GI}$ to be the class of all decision problems $L$ for which there is a polynomial-time Turing reduction from $L$ to $GraphIso$.

**Definition**: Let $\textbf{NP}^{\textbf{GI}}$ be the class all decision problems which can be decided by a polynomial-time non-deterministic Turing machine with access to an oracle for a problem which is in $\textbf{GI}$.

My question is then: is this class known? Is it equivalent to a more standard complexity class? Is there any know complete problem for this class?

**Tags:** cc.complexity-theory, graph-isomorphism

> **Comments:**
> **username_0**: It's interesting though that for $GI$, a problem $L$ is said to be $GI$-complete if and only if (1) $L$ is in $GI$ (i.e. there is a polynomial-time Turing reduction from $L$ to $GraphIso$) and (2) $L$ is $GI$-hard, which by definition means that there is a polinomial-time Turing reduction (not many-to-one reduction!) from $GraphIso$ to $L$. The more relaxed reductions used make this slightly different than what I would call a normal "nice" syntactic class...  
> **username_0**: I agree with this, but what about a natural $NP^{GI}$-complete problem?  
> **username_1**: @username_0: The bounded-time halting problem for nondeterministic machines with a GraphIso oracle should be complete for this class. Also, note that under a standard derandomization assumption (namely, $\mathsf{NP} = \mathsf{AM}$), we would have $\mathsf{NP}^{GI} = \mathsf{NP}$, since in this scenario GI would be in $\mathsf{NP} \cap \mathsf{coNP}$, which is low for $\mathsf{NP}$.  

---

## 1 answers

### Answer by username_1 on 2015-12-16. Score: 5

[Summarizing the answers in the comments by Ricky Demer and Josh Grochow.]

$\mathsf{NP}^{\mathsf{GI}} = \mathsf{NP}^{GraphIso}$, since these are nondeterministic poly-time *Turing* reductions, which can be simulated by the oracle machine (as detailed e.g. [here](https://cs.stackexchange.com/questions/26317/question-about-the-definition-of-complexity-class-oracles/26332#26332)).

The bounded-time halting problem for non-deterministic machines with a GraphIso oracle is complete for this class, by the usual proof.

Under standard derandomization assumptions (in particular, any that imply $\mathsf{AM} = \mathsf{NP}$), $\mathsf{NP}^{\mathsf{GI}} = \mathsf{NP}$, since under such assumption we have $\mathsf{GI} \subseteq \mathsf{NP} \cap \mathsf{coNP}$, and the latter is low for $\mathsf{NP}$.


---

