Можно ли решить изоморфизм графа с ограниченным квадратным недетерминизмом?

Ограниченность недетерминизм связывает функцию $g(n)$ с классом языков , принятых ресурсы ограничены детерминированные тьюринговых машинами, чтобы сформировать новый класс - . Этот класс состоит из тех языков, которые принимаются некоторой недетерминированной машиной Тьюринга подчиняющейся тем же границам ресурса, которые используются для определения , но где разрешено делать не более недетерминированных ходов. (Я использую обозначение Голдсмит, Леви и Мундхенк вместо оригинала Кинталы и Фишера, а - размер ввода.) $C$ $g$ $C$ $M$ $C$ $M$ $g(n)$ $n$

Мой вопрос:

Существует ли константа такая, что изоморфизм GRAPH находится в - ? $c\ge0$ $c\sqrt{n}$ $\mathsf{PTIME}$

( Правка: Джошуа Грохоу указал, что положительный ответ на этот вопрос подразумевает алгоритм для GI, который имеет лучшие асимптотические границы времени выполнения, чем известны в настоящее время. Поэтому я был бы рад ослабить ограничение, допуская недетерминированные ходы.) $o(\sqrt{n}\log n)$

Задний план

Для каждой фиксированной константы , - , поскольку недетерминированных ходов создает не более чем полиномиальное число конфигураций для детерминистического изучения. Более того, , и с помощью заполнения можно выставлять NP-полные языки в - для каждого . $c \ge 0$ $\mathsf{PTIME} = {c\log n}$ $\mathsf{PTIME}$ $c\log n$ $\mathsf{NP} = \cup_c n^c\text{-}\mathsf{PTIME}$ $n^\varepsilon$ $\mathsf{P}$ $\varepsilon > 0$

Кинтала и Фишер заметили, что решение о том, имеет ли -клике входной граф с вершинами -complete, но находится в - , Чтобы увидеть это, отбросим вершины, у которых не более соседей. Если оставшихся вершин слишком мало, отклоните. В противном случае оставшиеся вершины образуют граф размера . Тогда угадать -подмножество вершин, используя недетерминированных шагов и убедитесь, что они образуют клику за полиномиальное время. $V$ $(|V|/3)$ $\mathsf{NP}$ $O(\sqrt{n})$ $\mathsf{PTIME}$ $|V|/3 - 2$ $\Omega(|V|^2)$ $|V|/3$ $|V| = O(\sqrt{n})$

Некоторые другие языки плотных графов в также находятся в - . Это относится к любой проблеме, когда подмножество вершин служит сертификатом, а размер входного графа равен . Примерами являются многообещающие версии Induced Path или 3-Coloring для случая плотных графов. Другие проблемы, кажется, требуют больших сертификатов, например, список вершин, определяющих гамильтонову цепь, кажется, требует битов . Мне не ясно, можно ли использовать такое количество недетерминизма, которое слишком мало, чтобы угадать сертификат для решения таких проблем. $L$ $\mathsf{NP}$ $O(\sqrt{n})$ $\mathsf{PTIME}$ $\Omega(|V|^2)$ $\Omega(|V| \log |V|)$

Учитывая, что - может содержать NP-полные языки, тогда представляется интересным спросить, где в ограниченной иерархии недетерминированности потенциально легче упасть языки. Можно было бы ожидать, что GI, как язык, который не кажется NP-полным, окажется в иерархии ближе к - чем к - . Однако очевидный сертификат для GI указывает карту, используябиты, которые являются . $n^\varepsilon$ $\mathsf{P}$ $\log n$ $\mathsf{P}$ $n$ $\mathsf{P}$ $|V|\log |V|$ $\omega(\sqrt{n})$

Еще один способ подумать над этим вопросом: является ли указание карты между наборами вершин кратчайшим сертификатом для GI?

Изменить: Далее следуют некоторые (исправленные) замечания, касающиеся комментариев Джошуа Грохова.

Если сертификат использует биты и может быть проверен за полиномиальное время, то грубая сила дает алгоритм для GI, принимающий время. С сертификатом размера грубая сила дает алгоритму время , а сертификат размера дает метод грубой силы, занимающий времени. Давняя верхняя граница Лукса составляет времени, которое находится между этими двумя границами до постоянных показателей. $f(n) = \Omega(\log n)$ $poly(n)2^{O(f(n))} = 2^{O(f(n))}$ $O(\sqrt{n})$ $2^{O(\sqrt{n})}$ $O(\sqrt{n}\log n)$ $2^{O(\sqrt{n}\log n)}$ $2^{O(\sqrt{n\log n})}$

Эти соображения предполагают, что может быть альтернативный подход к GI. Подход Luks, кажется, основывается на идентификации подмножества генераторов ассоциированной группы. Поэтому недетерминированная машина может угадать подмножество группы. Эти подмножества могут быть затем тщательно проверены для получения детерминированного алгоритма Если список элементов может быть указан кратко, либо потому, что связанная группа никогда не намного больше, чем размер графа, либо потому, что число требуемых генераторов всегда мало, и проверка каждого подмножества кандидатов не занимает слишком много времени, тогда это может дать альтернативный подход к Г.И.

Чандра М.Р. Кинтала и Патрик К. Фишер, уточняющий недетерминизм в релятивизированных вычислениях с ограниченным полиномиальным временем , журнал SIAM по вычислениям 9 (1), 46–53, 1980. doi: 10.1137 / 0209003
Джуди Голдсмит, Мэтью А. Леви, Мартин Мундхенк, Ограниченный недетерминизм , SIGACT News 27 (2), 20–29, 1996. doi: 10.1145 / 235767.235769
László Babai и Eugene M. Luks, Каноническая маркировка графов , STOC 1983, 171–183. doi: 10.1145 / 800061.808746

cc.complexity-theory graph-theory graph-isomorphism nondeterminism Андраш Саламон
источник

Итак, если граф задан как матрица смежности размера

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

n^{2}

$n^2$

n

$n$

Джон Д.

@ user17410: Да, представление не должно иметь большого значения, если размер любого экземпляра равен

. (Если они необоснованно дополняются, чтобы иметь размер

тогда, конечно, достаточно ограничения квадратного корня.)

O (| V |^{2})

$O(|V|^2)$

Ω ((| V | \log | V |)^{2})

$\Omega((|V|\log|V|)^2)$

Андрас Саламон

Я думаю, что вы, возможно, просите алгоритм лучше, чем самый известный ... Если я понимаю,

алгоритм

даст

O (\sqrt{n}) - P T I M E

$O(\sqrt{n})-\mathsf{PTIME}$

детерминированный алгоритм. Текущий самый известный детерминированный алгоритм занимает время

2^{O (\sqrt{n})}

$2^{O(\sqrt{n})}$

2^{O (\sqrt{n} \log^{2} n)}

$2^{O(\sqrt{n} \log^2 n)}$

Джошуа Грохов

@ AndrásSalamon: грубая сила =

НЕ

n! p o l y (n) \approx 2^{O (n \log n)}

$n!poly(n) \approx 2^{O(n \log n)}$

... Кроме того, я не понимаю, почему сертификат размера

2^{O (\sqrt{n} \log^{2} n)}

$2^{O(\sqrt{n} \log^2 n)}$

приводит к алгоритму грубой силы времени

\sqrt{n}

$\sqrt{n}$

а не

2^{\sqrt{n} \log n}

$2^{\sqrt{n} \log n}$

- можешь уточнить? Может быть, я что-то упустил в определении нотации «PTIME»?

2^{O (\sqrt{n})}

$2^{O(\sqrt{n})}$

Джошуа Грохов

@ MohammadAl-Turkistany: Может быть, но мне придется немного подумать об этом. В алгоритме Бабая есть точки, где, когда степень цвета ниже многочлена, он применяет тест GI с ограниченной степенью, как в предыдущем лучшем алгоритме, и неясно, можно ли превратить либо тест многочлена GI в ограниченный полилогом недетерминизм, или можно ли продолжить рекурсию Бабая дальше, чтобы получить степень, скажем, до постоянной цветовой степени. Если и когда я это выясню, я обновлю свой ответ - если у вас есть мысли по этому поводу, я с удовольствием пообщаюсь, но, вероятно, это не подходящее место для проработки.

Джошуа

Во-первых, (как это было теперь отредактировано в формулировке вопроса) положительный ответ на ваш вопрос немедленно улучшил бы уровень техники в наихудших оценках для графа изоморфизма. Для алгоритм дает $O(\sqrt{n})-\mathsf{PTIME}$ -детерминистический алгоритм, но в настоящее время наиболее известным для GI является только $2^{O(\sqrt{n})}$ $2^{O(\sqrt{n \log n})}$

Во-вторых, мне даже не сразу понятно, является ли текущий лучший алгоритм действительно алгоритма, хотя первая его часть явно есть, в некотором смысле. Алгоритм сначала угадывает множество вершин размера $O(\sqrt{n \log n})-\mathsf{PTIME}$ индивидуализировать (трюк Zemlyachenko - смздесьдля экспозиции на английском языке), что может быть сделано путем угадывания $\sqrt{n/\log n}$ битов недетерминировано. Однако, после их угадывания и индивидуализации (в детерминированном много времени), он применяет самый известный тест изоморфизма ограниченной степени, который занимает время (теорема 9.1этой статьи), и применяет его в случай $\sqrt{n \log n}$ $n^{O(d /\log d)}$ . Я должен тщательно подумать о том, можно ли превратить последний алгоритм в $d=O(\sqrt{n \log n})$ алгоритм(кажется интересным вопросом ...) $O(\sqrt{n \log n})-\mathsf{PTIME}$

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

У вас есть ссылки на версии не за платным доступом? Я никогда не видел реальной реализации уловки Земляченко или теста изоморфизма ограниченной степени. Разделение вершин по степени, например, NAUTY, ускоряет процесс, но тем, у кого такая же степень, вам все равно придется проверять все перестановки простых циклов на них AFIK.

Чад Brewbaker

@Chad: я, к сожалению, не знаю о неоплаченных версиях этих статей. Однако уловка Земляченко довольно проста для реализации на практике и существенно снижает степень. Для практической реализации трюка Земляченко, я думаю, что единственным вопросом является компромисс между перечислением наборов вершин для индивидуализации (экспоненциальный по размеру набора) и любыми потенциальными выгодами, полученными путем эффективного уменьшения степени. Я не знаю, реализовано ли это в NAUTY или других практических алгоритмах изоморфизма.

Джошуа Грохов

@Chad: Кстати, тестирования перестановок простых циклов достаточно только для обнаружения нетривиального автоморфизма; этого недостаточно для проверки изоморфизма. Например, если

- граф без нетривиальных автоморфизмов, пусть

- любая перестановка - не обязательно простой цикл. Тогда

изоморфно

, и

является единственным изоморфизмом между

. Но этот изоморфизм не будет обнаружен только при рассмотрении простых циклов.

G

$G$

π

$\pi$

π (G)

$\pi(G)$

G

$G$

π

$\pi$

G

$G$

π (G)

$\pi(G)$

Джошуа Грохов

Ценой удвоения

можно вычислить ISO с помощью AUT, поместив оба графика в матрицу смежности.

n

$n$

Чад Brewbaker

@Chad: если вы это сделаете, то уже есть

перестановки простых циклов порядка 2, так что вы потеряли потенциальную экономию. Это связано с тем, что вы описываете сокращение от ISO до вычисления генераторной установки для группы автоморфизмов. Не существует известного сокращения времени по времени от ISO до проблемы простого решения, имеет ли граф нетривиальный автоморфизм.

n!

$n!$

Джошуа Грохов

Можно ли решить изоморфизм графа с ограниченным квадратным недетерминизмом?

Задний план

Ответы: