certificado de coNP para isomorfismo gráfico

Es fácil ver que el isomorfismo gráfico (IG) está en NP. Es un gran problema abierto si GI está en coNP. ¿Hay posibles candidatos de propiedades de gráficos que se puedan usar como certificados coNP de IG? ¿Alguna conjetura que implique ? ¿Cuáles son algunas implicaciones de G I ∈ c o N P ?$GI \in coNP$$GI \in coNP$

Si está en c o N P , entonces tendríamos el resultado: G I no es N P -Complete menos N P = c o N P = P H . (Actualmente conocido: G I no es N P -completo a menos que Σ 2 P = Π 2 P = P H ).$GI$$coNP$$GI$$NP$$NP=coNP=PH$$GI$$NP$$\Sigma_2 P = \Pi_2 P = PH$

Dado que está en c o A M , obviamente desrandomizar c o A M ( enlace doi ) pondría G I ∈ c o N P , pero no conozco ninguna propiedad de gráfico candidato para poner G I ∈ c o N P de otra manera. ¡Espero más respuestas!$GI$$coAM$$coAM$$GI \in coNP$$GI \in coNP$

Curiosamente, en que el papel También muestran que el gráfico no isomorfismo tiene pruebas de tamaño subexponenciales - es decir, - a menos que P H = Σ 3 P . Esto es al menos dirigido en la dirección de mostrar condicionalmente que G I ∈ c o N P .$GI \in co NSUBEXP$$PH = \Sigma_3 P$$GI \in coNP$

¿Qué tal el rango (es decir, lista, una entrada por borde) de resistencias efectivas? La resistencia efectiva de un borde es la probabilidad de que el borde esté en un árbol de expansión aleatorio. Se pueden encontrar resistencias efectivas utilizando algoritmos de Spielman y Teng, aunque no sé qué tan fácil es implementarlo realmente (si se quisiera hacer experimentos).

Supongamos que tenemos dos gráficos muy regulares, que tienen los mismos valores propios (y sabemos que los valores propios no distinguen necesariamente entre los gráficos no isomórficos). Entonces, si las resistencias efectivas (es decir, las listas, de nuevo) son las mismas, no se pueden usar para distinguir los gráficos. Pero, ¿por qué dos gráficos co-espectrales tendrían la misma distribución de sus bordes en árboles de expansión aleatoria? ¿Existe una conexión conocida entre el espectro del gráfico y las resistencias efectivas de un gráfico? es decir, conociendo el espectro gráfico, ¿podemos calcular las resistencias efectivas?

Podría ser interesante señalar que si GI no está en coNP, entonces P ≠ NP.

1) Si GI no está en coNp, entonces GI ≠ NGI

2) Si GI ≠ NGI entonces GI ≠ P

3) Si GI ≠ P entonces P ≠ NP

Como corolario de las proposiciones anteriores tenemos: si GI no está en coNP entonces P ≠ NP. Lo mismo ocurre si NGI no está en NP.