Каковы известные оценки сложности автоморфизма нетривиальных графов?

Для любого простого неориентированного графа G нетривиально определить, имеет ли G нетривиальные (неединичные) автоморфизмы. Но каковы результаты на верхних / нижних границах этой проблемы решения?

cc.complexity-theory graph-isomorphism automorphism Чарльз Ю
источник

Ответы:

Определение наличия у графа нетривиального автоморфизма Кука-сводит (полиномиальное время Тьюринга) к изоморфизму графа (определить, изоморфна ли пара графов) (упражнение для читателя). Не известно, что это эквивалентно изоморфизму графа.

В свою очередь, изоморфизм графов может быть решен за времени и лежит в . В частности, он не является полным, если не разрушится полиномиальная иерархия. $2^{\tilde O(\sqrt{n})}$ $NP \cap coAM$ $NP$

Джошуа Грохов
источник

Так ? Я думал, что многие сводят к . Я ошибся? Также известно или даже это вне досягаемости?

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}$

Т ....