Взаимосвязь между симметрией и вычислительной непроницаемостью?

16

-fixed точки без проблем автоморфизма запрашивает автоморфизм графа , который перемещается по крайней мере , к ( п ) узлы. Проблема в том, что N P- полна, если k ( n ) = n c для любого c > 0.kk(n)NPk(n)=ncc

Однако, если то задача полиномиального времени Тьюринга сводится к проблеме изоморфизма графов. Если k ( n ) = O ( log n / log log n ), то задача полиномиального времени тьюрингова эквивалентна задаче автоморфизма графа, которая находится в N P I и неизвестно, что N P -полна. Задача об автоморфизме графа сводится по Тьюрингу к проблеме изоморфизма графа.k(n)=O(logn)k(n)=O(logn/loglogn)NPINP

О сложности подсчета числа вершин, перемещаемых графомными автоморфизмами, Антони Лозано и Виджей Рагхаван, Фонд программных технологий, LNCS 1530, с. 295–306

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

Есть ли еще один пример сложной проблемы, которая поддерживает эту связь между симметрией и твердостью?

Мухаммед Аль-Туркистани
источник
Пожалуйста, добавьте ссылку на результат NP-полноты для автоморфизма без k-неподвижной точки. Благодарю.
Мартин Шварц,
1
Автоморфизм графа неизвестен в NPI.
Эмиль
@ Эмиль: В NPI ничего не известно , так как мы не знаем ! Но GA, как и GI, не является NP-полной, если только PH не рухнет. OTOH, у нас действительно нет никаких оснований думать, что это не в P, кроме того, что люди пытались и потерпели неудачу. PNP
Джошуа Грохов
1
@turkistany: Отличный вопрос!
Джошуа Грохов
1
@ Джошуа: Да, я знаю. Я просто предлагал исправить текст вопроса.
Эмиль

Ответы:

14

Это не совсем то же самое отношение между симметрией и твердостью, но существует тесная связь между симметриями булевой функции и сложностью ее схемы. Видеть:

Бабаи Л., Билс Р. и Такаччи-Надь П. Симметрия и сложность , STOC 1992.

Вот что они показывают. Пусть - последовательность групп перестановок. Обозначим через s ( G i ) число орбит G i, вызванных его действием на { 0 , 1 } i (путем перестановки координат). Обозначим через F ( G ) класс языков L, такой что L { 0 , 1 } n инвариантен относительно G n . Тогда все языки в FGiSis(Gi)Gi{0,1}iF(G)LL{0,1}nGn есть схемы размера не более р ø л у ( х ( G ) ) и глубиной не более р ø л у ( журнал ( ы ( G ) ) , и это,существужесткой.F(G)poly(s(G))poly(log(s(G))


В обратном направлении несколько задач которых наборы свидетелей имеют много симметрий, оказываются в c o A M (подобно G I ), и поэтому не являются N P- неполными, если P H не разрушится. Фактически, следующая статья показывает, что задачи N P, у которых множество свидетелей имеет много симметрий, являются низкими для P P :NPcoAMGINPPHNPPP

Арвинд В., Винодчандран Н. В. Сложность подсчета определяемых группой языков . ТМФ. Вычи. Sci. 242 (2000), нет. 1-2, 199-218.

PPNPPPPHBPPPBPPP=PPNPPPPPNPNPPP


ff(x)=f(y)xyNP


Наконец, программа теории геомектрической сложности Малмулей-Сохони по существу использует симметрию для доказательства твердости, хотя связь симметрии с твердостью здесь более тонкая и менее прямая.

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

Структурированные экземпляры SAT, которые обладают множеством симметрий, кажутся более простыми для решения, чем случайные экземпляры SAT. Кодирование реальных проблем в SAT всегда порождает структурированные экземпляры (что неудивительно, поскольку у реальных проблем, с которыми мы сталкиваемся, есть симметрии). Лучшие полные решатели SAT способны эффективно решать случаи в реальном мире с 1 000 000 переменных, но ни одна из них, насколько я знаю, не способна эффективно решать случайные случаи, скажем, с 10 000 переменных (по Эдварду А. Хиршу На домашней странице можно найти несколько неожиданно небольших случайных примеров, на которые могут застрять даже лучшие полные решатели SAT. Таким образом, с эмпирической точки зрения наличие симметрии, по-видимому, уменьшает твердость.

Джорджио Камерани
источник