0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ That is a "nice" syntactic class, so it certainly has a compete problem. $\;$ $\endgroup$ – user6973 Oct 20 '15 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 '15 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 '15 at 20:44
  • $\begingroup$ I agree with this, but what about a natural $NP^{GI}$-complete problem? $\endgroup$ – gdiazc Oct 20 '15 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$ – Joshua Grochow Oct 21 '15 at 2:48
5
$\begingroup$

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

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