Вдохновленный вопросом, что факторинг известен как P-hard , мне интересно, каково текущее подобное состояние знаний о твердости изоморфизма графов. Я уверен, что в настоящее время неизвестно, находится ли G в P, но:
какой самый известный в настоящее время класс, чем GI сложнее?
(не было ответа на похожий вопрос )
Чтобы обратиться к некоторым комментариям, я хочу знать известный в настоящее время максимальный класс (ы), для которого GI, проблема завершена. Известные алгоритмы для GI ограничены сверху суперполиномиальными функциями, и он является членом NP. Но не известно, что G-это P-hard. Я хотел бы знать любые классы C, для которых известно, что это C-hard, и, надеюсь, как можно более инклюзивно.
Ответы:
Изоморфизм графов труден для DET, класса задач, которые сводятся к определителю. См. «О твердости изоморфизма графов» Якобо Торана. http://epubs.siam.org/sicomp/resource/1/smjcat/v33/i5/p1093_s1?isAuthorized=noNС1
Кажется, это самый сильный результат твердости на сегодняшний день.
источник