Resultados negativos en el enfoque de partículas idénticas al problema del isomorfismo gráfico (GI)

12

Se han realizado algunos esfuerzos para atacar el problema del isomorfismo gráfico utilizando la caminata aleatoria cuántica de bosones de núcleo duro (simétrica pero sin ocupación doble). Amir Rahnamai Barghi e Ilya Ponomarenko demostraron que el poder simétrico de la matriz de adyacencia, que parecía prometedor, era incompleto para los gráficos generales en este documento . Otro enfoque similar también fue refutado en este artículo por Jamie Smith. En ambos artículos, utilizan la idea de una configuración coherente (esquemas) y una formulación alternativa pero equivalente de álgebra celular (subalgebra matricial indexada por un conjunto finito -aquí conjunto de vértices- cerrado bajo multiplicación puntual, transposición de conjugado complejo y que contiene Matriz de identidad I y matriz todo en unoJ ) respectivamente para proporcionar los contraargumentos necesarios.

Me resulta muy difícil seguir esos argumentos e incluso si sigo vagamente argumentos individuales no entiendo la idea central. Me gustaría saber si la esencia de los argumentos puede explicarse en términos genéricos, puede ser a costa de un ligero rigor, sin utilizar el lenguaje de la teoría de esquemas o el álgebra celular.

DurgaDatta
fuente

Respuestas:

4

¡Puedes hacerlo mucho mejor que marcar todos los n! permutaciones cuando el bruto fuerza una solución, http://oeis.org/A186202. El grial muestra que no se puede hacer mucho mejor que eso, o explota el hecho de que la mayoría de los gráficos no tienen simetría y utilizan esto para acelerar el cálculo.

Chad Brewbaker
fuente
2
El documento suyo al que se hace referencia desde OEIS muestra un límite en el tamaño de un conjunto modo que cruza con cada subgrupo no trivial de . Probablemente estoy siendo lento aquí, pero ¿cómo te ayuda tener un conjunto de este tipo a resolver a) el problema de subgrupo oculto para ob) isomorfismo gráfico (un caso especial de (a))? SSnSSnSn
Joshua Grochow
1
Si prueba una permutación no trivial de cada ciclo principal, ha verificado todos los subgrupos posibles de Sn. Sigue siendo enorme. Además, es para verificar el automorfismo gráfico que es "más fácil" que el isomorfismo.
Chad Brewbaker