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?

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

1 Answer 1


[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).

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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