# Complete problems or alternative definitions of the complexity class NP^GI?

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?

• That is a "nice" syntactic class, so it certainly has a compete problem. $\;$ – user6973 Oct 20 '15 at 17:06
• 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 Oct 20 '15 at 20:38
• NP$^{\text{GI}}$ = NP$^{\text{GraphIso}} \:$, $\:$ since NP can also use the reduction to simulate the oracle queries. $\;\;\;\;$ – user6973 Oct 20 '15 at 20:44
• I agree with this, but what about a natural $NP^{GI}$-complete problem? – gdiazc Oct 20 '15 at 21:05
• @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 Oct 21 '15 at 2:48

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