O isomorfismo do gráfico está no UP coUP?

O isomorfismo do gráfico (o problema de decisão) está em ? Aqui é a classe de problemas de decisão aceitos por uma máquina de Turing inequívoca (consulte o zoológico da complexidade ).$\mathsf{UP}\cap \mathsf{coUP}$$\mathsf{UP}$

O isomorfismo do gráfico não é conhecido em nem em .c o U $\mathsf{UP}$$\mathsf{coUP}$

Para : o algoritmo não determinístico natural - adivinhe um mapa entre os dois gráficos e verifique se é um isomorfismo - tem 0 testemunhas (se os gráficos não forem isomorfos) outestemunhas. Embora a maioria dos gráficos tenha (ou seja, se você escolher um gráfico aleatório em vértices, a probabilidade de ele ter qualquer automorfismo não trivial vai para rapidamente com ), isso não é basta dizer que sempre há no máximo uma testemunha. É claro que isso não descarta outro algoritmo que possa mostrar o isomorfismo do gráfico em . (Afinal, é possível que o isomorfismo gráfico esteja| Aut ( G ) | | Aut ( G ) | = 1 n 0 n U P P ⊆ U $\mathsf{UP}$$|\text{Aut}(G)|$$|\text{Aut}(G)|=1$$n$$0$$n$$\mathsf{UP}$$\mathsf{P} \subseteq \mathsf{UP}$ .)

Quanto a , como apontado por Peter Shor, nem sabemos se o isomorfismo do gráfico está em , portanto, certamente não sabemos se está em . (Sob uma suposição plausível de derandomização, ela está em , mas não conheço nenhuma suposição natural que a coloque em ou .)C O N P C O L P C O N P L P C O L $\mathsf{coUP}$$\mathsf{coNP}$$\mathsf{coUP}$$\mathsf{coNP}$$\mathsf{UP}$$\mathsf{coUP}$