Complexidade da computação Lexicographically Minimal Element of Orbit

Claramente, o isomorfismo de cordas, no sentido de Babai, é redutível a esse problema, pois, dadas as cordas e o grupo G , podemos simplesmente encontrar seus representantes mínimos de órbita como acima e compará-los diretamente, mas não está claro que se o isomorfismo de cordas for fácil, então isso sendo fácil segue. Vou ver se o artigo de Babai indica como fazer isso. $x, y$$G$

O artigo de Babai não aborda essa questão; na pág. 11 ele diz explicitamente que o papel não lida com a questão das formas normais. Isso não quer dizer que as técnicas não possam ser úteis para encontrar uma forma normal, mas isso seria uma contribuição não trivial.

Obrigado @JoshuaGrochow Não tenho certeza se tenho experiência em usar essas técnicas, mas verei o que posso fazer. É adequadamente difícil, mesmo que seja quase-polinomial que não seja mais útil para mim da maneira que eu queria usá-lo.

Se você estiver interessado em soluções concretas para esse problema, recomendo que você dê uma olhada nas publicações de T. Junttila (a quem cito em minha resposta), especialmente sua tese de doutorado e seu trabalho sobre isomorfismo e simetrias de grafos em geral.