Kompleksitas Komputasi Elemen Minimal Orbit Leksikografis

Jelas isomorfisma string dalam arti Babai dapat direduksi menjadi masalah ini, seperti yang diberikan string dan grup G kita dapat dengan mudah menemukan perwakilan orbit minimal mereka seperti di atas dan langsung membandingkannya, tetapi tidak jelas bahwa jika string isomorfisma mudah maka ini menjadi mudah diikuti. Saya akan melihat apakah kertas Babai menunjukkan bagaimana melakukan ini. $x, y$$G$

Makalah Babai tidak membahas pertanyaan ini; pada p. 11 dia secara eksplisit mengatakan bahwa makalah mereka tidak berurusan dengan pertanyaan tentang bentuk normal. Itu bukan untuk mengatakan teknik tidak bisa berguna untuk menemukan bentuk normal, hanya saja dengan melakukan itu akan menjadi kontribusi non-sepele.

Terima kasih @ JoshuaGrochow. Saya tidak yakin apakah saya memiliki latar belakang untuk menggunakan teknik ini tetapi saya akan melihat apa yang bisa saya lakukan. Sangat sulit bahkan jika itu quasipolynomial bahwa itu tidak lagi berguna bagi saya dalam cara saya ingin menggunakannya.

Jika Anda tertarik pada solusi konkret untuk masalah ini, saya sarankan Anda melihat publikasi T. Junttila (yang saya kutip dalam jawaban saya), terutama tesis PhD-nya dan karyanya pada grafik isomorfisme dan simetri pada umumnya.