apa yang diketahui batas pada kompleksitas automorfisme grafik nontrivial

Diberikan grafik G sederhana yang tidak terarah, adalah nontrivial untuk menentukan apakah G memiliki automorfisme nontrivial (bukan identitas). Tetapi apa hasil pada batas atas / bawah masalah keputusan ini?

cc.complexity-theory graph-isomorphism automorphism Charles Yu
sumber

Jawaban:

Menentukan apakah suatu grafik memiliki automorfisme nontrivial. Cook-reduced (waktu polinomial Turing) menjadi Grafik Isomorfisme (tentukan apakah sepasang grafik isomorfis) (latihan untuk pembaca). Itu tidak diketahui setara dengan isomorfisme grafik.

Pada gilirannya, grafik isomorfisma dapat diselesaikan dalam waktu dan kebohongan di. Secara khusus, itu bukan-Lengkap kecuali hirarki polinomial runtuh. $2^{\tilde O(\sqrt{n})}$ $NP \cap coAM$ $NP$

Joshua Grochow
sumber

G A \in P^{G I}

$GA\in P^{GI}$

G A

$GA$

G I

$GI$

G I \in B P P^{G A}

$GI\in BPP^{GA}$