Resultados negativos na abordagem de partículas idênticas ao problema do isomorfismo de grafos (IG)

12

Houve alguns esforços para atacar o problema do isomorfismo de grafos usando a caminhada aleatória quântica de bósons do núcleo duro (simétrica, mas sem ocupação dupla). O poder simétrico da matriz de adjacência, que parecia promissor, mostrou-se incompleto para gráficos gerais neste artigo por Amir Rahnamai Barghi e Ilya Ponomarenko. Outra abordagem semelhante também foi refutada neste artigo por Jamie Smith. Em ambos os trabalhos, eles usam a idéia de configuração coerente (esquemas) e formulação alternativa, mas equivalente, de álgebra celular (subalgebra matriz indexada por um conjunto finito - aqui vértice - fechado sob multiplicação pontual, transposição conjugada complexa e contendo Matriz de identidade I e matriz tudoJ ), respectivamente, para fornecer contra-argumentos necessários.

Acho muito difícil seguir esses argumentos e, mesmo que sigo vagamente argumentos individuais, não entendo a idéia central. Gostaria de saber se a essência dos argumentos pode ser explicada em termos genéricos - pode custar um pouco de rigidez - sem usar a linguagem da teoria de esquemas ou da álgebra celular.

DurgaDatta
fonte

Respostas:

4

Você pode fazer muito melhor do que verificar todos os n! permutações ao forçar brutalmente uma solução, http://oeis.org/A186202 O graal está mostrando que você não pode fazer muito melhor do que isso, ou explorando o fato de que a maioria dos gráficos não tem simetria e usa isso para acelerar o cálculo.

Chad Brewbaker
fonte
2
SSnSSnSn
1
Se você testar uma permutação não trivial de cada ciclo principal, você verificou todos os subgrupos possíveis de Sn. Ainda é enorme. Além disso, é para verificar o automorfismo gráfico que é "mais fácil" que o isomorfismo.
Chad Brewbaker