¿Es el isomorfismo gráfico en UP coUP?

¿Es el isomorfismo gráfico (el problema de decisión) en ? Aquí es la clase de problemas de decisión aceptados por una máquina de Turing inequívoca (ver el zoológico de complejidad ).$\mathsf{UP}\cap \mathsf{coUP}$$\mathsf{UP}$

No se sabe que el isomorfismo gráfico está en ni en .$\mathsf{UP}$$\mathsf{coUP}$

Para : el algoritmo natural no determinista - adivine un mapa entre los dos gráficos y verifique si es un isomorfismo - tiene 0 testigos (si los gráficos no son isomorfos) otestigos. Aunque la mayoría de los gráficos tienen (es decir, si elige un gráfico aleatorio en vértices, la probabilidad de que tenga automorfosimatos no triviales va a bastante rápido con ), esto no es suficiente para decir que siempre hay como máximo un testigo. Por supuesto, esto no descarta algún otro algoritmo que pueda mostrar ese isomorfismo gráfico en . (Después de todo, es posible que el isomorfismo gráfico esté en$\mathsf{UP}$$|\text{Aut}(G)|$$|\text{Aut}(G)|=1$$n$$0$$n$$\mathsf{UP}$$\mathsf{P} \subseteq \mathsf{UP}$ .)

En cuanto a , como lo señaló Peter Shor, ni siquiera sabemos si el isomorfismo gráfico está en , por lo que ciertamente no sabemos si está en . (Bajo un supuesto plausible de desrandomización está en , pero no conozco ningún supuesto natural que lo en o .)$\mathsf{coUP}$$\mathsf{coNP}$$\mathsf{coUP}$$\mathsf{coNP}$$\mathsf{UP}$$\mathsf{coUP}$