L'isomorphisme du graphe est-il dans UP coUP?

L'isomorphisme du graphe (le problème de décision) est-il dans ? Ici est la classe de problèmes de décision acceptée par une machine de Turing sans ambiguïté (voir le zoo de la complexité ).$\mathsf{UP}\cap \mathsf{coUP}$$\mathsf{UP}$

L'isomorphisme du graphe n'est pas connu pour être dans ni pour être dans .$\mathsf{UP}$$\mathsf{coUP}$

Pour : l'algorithme non déterministe naturel - devinez une carte entre les deux graphiques et vérifiez s'il s'agit d'un isomorphisme - a soit 0 témoins (si les graphiques ne sont pas isomorphes) oules témoins. Bien que la plupart des graphiques aient (c'est-à-dire, si vous choisissez un graphique aléatoire sur sommets, la probabilité qu'il ait des automorphismes non triviaux passe à assez rapidement avec ), ce n'est pas assez pour dire qu'il y a toujours au plus un témoin. Bien sûr, cela n'exclut pas un autre algorithme qui pourrait montrer cet isomorphisme de graphe dans . (Après tout, il est possible que l'isomorphisme du graphe soit$\mathsf{UP}$$|\text{Aut}(G)|$$|\text{Aut}(G)|=1$$n$$0$$n$$\mathsf{UP}$$\mathsf{P} \subseteq \mathsf{UP}$ .)

Quant à , comme l'a souligné Peter Shor, nous ne savons même pas si l'isomorphisme du graphe est dans , donc nous ne savons certainement pas s'il est dans . (Sous une hypothèse de dérandomisation plausible, il se trouve dans , mais je ne connais aucune hypothèse naturelle qui le place dans ou .)$\mathsf{coUP}$$\mathsf{coNP}$$\mathsf{coUP}$$\mathsf{coNP}$$\mathsf{UP}$$\mathsf{coUP}$