certificado coNP para isomorfismo gráfico

É fácil ver que o isomorfismo do gráfico (IG) está no PN. É um grande problema em aberto se a IG está no coNP. Existem candidatos potenciais às propriedades dos gráficos que podem ser usados ​​como certificados coNP de IG. Alguma conjectura que implique ? Quais são algumas implicações de ?$GI \in coNP$$GI \in coNP$

Se estiver em , teríamos o resultado: não é completo, a menos que . (Atualmente conhecido: não é menos que ).$GI$$coNP$$GI$$NP$$NP=coNP=PH$$GI$$NP$$\Sigma_2 P = \Pi_2 P = PH$

Desde está em , obviamente derandomizing ( ligação doi ) iria colocar , mas eu não sei de quaisquer propriedades gráfico candidato para colocar contrário. Estou ansioso para obter mais respostas!$GI$$coAM$$coAM$$GI \in coNP$$GI \in coNP$

Curiosamente, em que o papel que eles também mostram que Graph não-Isomorfismo tem provas tamanho subexponencial - isto é, - a menos . Isso é pelo menos direcionado a mostrar condicionalmente que .$GI \in co NSUBEXP$$PH = \Sigma_3 P$$GI \in coNP$

E quanto à faixa (ou seja, lista, uma entrada por aresta) de resistências efetivas? A resistência efetiva de uma aresta é a probabilidade de que ela esteja em uma árvore de abrangência aleatória. Resistências efetivas podem ser encontradas usando os algoritmos de Spielman e Teng, embora eu não saiba como é fácil implementar (se alguém quiser fazer experimentos).

Suponha que tenhamos dois gráficos fortemente regulares, que têm os mesmos valores próprios (e sabemos que os valores próprios não distinguem necessariamente entre gráficos não isomórficos). Então, se as resistências efetivas (ou seja, as listas, novamente) são as mesmas, elas não podem ser usadas para distinguir os gráficos. Mas por que dois gráficos co-espectrais teriam a mesma distribuição de suas arestas em árvores aleatórias? Existe uma conexão conhecida entre o espectro do gráfico e as resistências efetivas de um gráfico? isto é, conhecendo o espectro gráfico, podemos calcular as resistências efetivas?

Pode ser interessante ressaltar que, se GI não estiver no coNP, então P ≠ NP.

1) Se GI não estiver em coNp, então GI ≠ NGI

2) Se GI ≠ NGI, então GI ≠ P

3) Se GI ≠ P então P ≠ NP

Como corolário das proposições acima, temos: se GI não está no coNP, então P ≠ NP. O mesmo vale se o NGI não estiver no NP.