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

10

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

Fayez Abdlrazaq Deab
fonte
5
O isomorfismo do gráfico está em UP. No entanto, , e não sabemos se o isomorfismo do gráfico está no , então a resposta é: não sabemos. coUPcoNPcoNP
Peter Shor
4
Posso obter uma referência para isomorfismo gráfico em UP?
precisa saber é o seguinte
6
@ PeterShor: Fiquei com a impressão de que o IG não era conhecido em UP ... O conjunto de isomorfismos entre dois gráficos tem cardinalidade 0 ou igual ao tamanho do grupo automorfismo de um dos gráficos, então o "natural "O algoritmo NP certamente não é um algoritmo UP. Você tinha algum outro algoritmo não determinístico para GI em mente que é um algoritmo UP?
Joshua Grochow
4
@ Josué: você está certo. Não se sabe que GI está em UP.
Peter Shor
11
GI é pelo menos na SZK, a classe Estatística Zero-Knowledge; por contenções conhecidas, portanto, também está em AM, coAM e coNP / poli (coAM está em coNP / poli por derandomização não uniforme normal). Este papel, por exemplo, discute os limites superiores conhecidos na SZK: cs.ucla.edu/~sahai/work/web/2003%20Publications/J.ACM2003.pdf
Andy Drucker

Respostas:

19

O isomorfismo do gráfico não é conhecido em nem em .c o U PUPcoUP

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 PU PUP|Aut(G)||Aut(G)|=1n0nUPPUP .)

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 PcoUPcoNPcoUPcoNPUPcoUP

Joshua Grochow
fonte