Какова текущая известная твердость изоморфизма графов?

21

Вдохновленный вопросом, что факторинг известен как P-hard , мне интересно, каково текущее подобное состояние знаний о твердости изоморфизма графов. Я уверен, что в настоящее время неизвестно, находится ли G в P, но:

какой самый известный в настоящее время класс, чем GI сложнее?

(не было ответа на похожий вопрос )

Чтобы обратиться к некоторым комментариям, я хочу знать известный в настоящее время максимальный класс (ы), для которого GI, проблема завершена. Известные алгоритмы для GI ограничены сверху суперполиномиальными функциями, и он является членом NP. Но не известно, что G-это P-hard. Я хотел бы знать любые классы C, для которых известно, что это C-hard, и, надеюсь, как можно более инклюзивно.

Митч
источник
2
"не было ответа на похожий вопрос" Неужели? Я думаю, что ответ Джошуа Грохова там отвечает на вопрос здесь.
Тайсон Уильямс
Посмотрите раздел «GI класса сложности» здесь: en.wikipedia.org/wiki/Graph_isomorphism_problem
Аарон Стерлинг,
3
@ Тайсон, и кто бы ни проголосовал за его комментарий: я думаю, что Митч говорит, что ответ там дает только верхние оценки изоморфизма графа, а не твердость изоморфизма графа.
Цуёси Ито
Я хотел бы добавить, что я не считаю это дублирующим вопросом. Ответ Джошуа дает верхние границы. Этот вопрос звучит больше как «GI хотя бы AC0 тяжело?» - да, согласен с @Tsuyoshi.
Аарон Стерлинг
6
Для плоских графиков известно, что они полны для L ... См. Theorie.informatik.uni-ulm.de/Personen/toran/beatcs/…
Джошуа Херман

Ответы:

22

Изоморфизм графов труден для DET, класса задач, которые сводятся к определителю. См. «О твердости изоморфизма графов» Якобо Торана. http://epubs.siam.org/sicomp/resource/1/smjcat/v33/i5/p1093_s1?isAuthorized=noNC1

Кажется, это самый сильный результат твердости на сегодняшний день.

Матеус де Оливейра Оливейра
источник
отличная ссылка (и с дополнительной нагрузкой на глаза на их странице, кажется, около 2004 года).
Митч
Действительно, это хорошая статья.
Матеус де Оливейра Оливейра