A prova de que problema Graph isomorfismo não é -completo

O problema de isomorfismo gráfico é um dos problemas mais antigos que resistiram à classificação em problemas ou . Temos evidências de que não pode ser completo. Em primeiro lugar, o isomorfismo do gráfico não pode ser completo, a menos que a hierarquia polinomial [1] desmorone para o segundo nível. Além disso, a versão de contagem [2] de GI é Turing em tempo polinomial equivalente à sua versão de decisão, que não se aplica a nenhum completo de conhecido . A versão de contagem de completos de parece ter uma complexidade muito maior. Finalmente, o resultado baixo [3] do IG em relação ao ( ) não é conhecido por conter nenhumN P N P N P N P N P P P P P L I = P P N $P$$NP$$NP$$NP$$NP$$NP$$PP$$PP^{GI}=PP$$NP$ problema completo. O resultado baixo da IG foi aprimorado para depois que Arvind e Kurur provaram que a IG está em [4].S P $SPP^{GI}=SPP$$SPP$

Que outros resultados (recentes) podem fornecer evidências adicionais de que o IG não pode ser completo?$NP$

Publiquei a pergunta no Mathoverflow sem obter resposta.

[1]: Uwe Schöning, "O isomorfismo dos grafos está na baixa hierarquia", Anais do 4º Simpósio Anual de Aspectos Teóricos da Ciência da Computação, 1987, 114-124

[2]: R. Mathon, "Uma nota no problema de contagem de isomorfismos nos gráficos", Information Processing Letters, 8 (1979), pp. 131–132

[3]: Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1992), "O isomorfismo do gráfico é baixo para PP", Computational Complexity 2 (4): 301–330

[4]: V. Arvind e P. Kurur. O isomorfismo do gráfico está em SPP, ECCC TR02-037, 2002.

Devido ao recente resultado de Babai (veja o artigo ), está em um tempo quase polinomial ( Q P ). Se G I é N P completo, então implica N P ⊆ Q P = D T I M E ( n p o l y l o $GI$$QP$$GI$$NP$. Isso, por sua vez, implicaEXP=NEXP, veja aqui. Portanto, se a conjectura comumente aceitaEXP≠NEXPé válida, entãoGInão pode serNPcompleto.$NP\subseteq QP=DTIME(n^{polylog\, n})$$EXP=NEXP$$EXP\neq NEXP$$GI$$NP$