Действительно ли алгоритм

13

У меня есть (надеюсь, простой, возможно, глупый) вопрос об исторической работе Бабая, показывающей, что является квазиполиномиальным.граммя

Бабай показал, как получить сертификат, что два графа для i { 1 , 2 } изоморфны по времени, квазиполиномиальны по v = | V я | ,граммязнак равно(Вя,Ея)я{1,2}vзнак равно|Вя|

Действительно ли Бабай показал, как найти элемент который переставляет вершины из G 1 в G 2 , или сертификат является просто утверждением о существовании?πSvграмм1грамм2

Если оракул говорит мне, что и G 2 изоморфны, нужно ли мне просматривать все v ! перестановки вершин?грамм1грамм2v!

Я спрашиваю, потому что я также думаю об эквивалентности узлов. Насколько я знаю, это не известно , будет, но сказать , обнаружение тривиального были в . На самом деле, нахождение последовательности движений Рейдемейстера, которые развязывают узел, может занять экспоненциальное время ...п

Метки
источник

Ответы:

28

N+1NN+2N+1,...N+N

domotorp
источник
1
Благодарность! Будут ли подобные гаджеты работать, чтобы показать набор движений Рейдемейстера, связывающих два узла друг с другом, учитывая только то, что они эквивалентны друг другу, или это не известно?
Марк С
3
Я сомневаюсь, поскольку в этом случае я не вижу способа «испортить» возможное решение.
домоторп
17

Более конкретно к алгоритму Бабая: да, алгоритм не только находит изоморфизм, он находит генераторы группы автоморфизмов (и, следовательно, эффективно находит все изоморфизмы) как часть алгоритма, то есть без сокращения ответа домоторпа.

С точки зрения принятия решения о существовании изоморфизма (или отсутствия связи) против его фактического поиска, ключевое слово для поиска - «поиск против решения» или «поиск до решения» («сокращение поиска до решения» и т. Д.). Такое сокращение известно для изоморфизма графов, а также для NP-полных задач, но это открытый вопрос для более алгебраических структур, таких как группы, и, я полагаю, узлов, именно потому, что мы не знаем, как добавить "гаджеты "как в ответе домоторпа.

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