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

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

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

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

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

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

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

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

Вот что они показывают. Пусть - последовательность групп перестановок. Обозначим через s ( G i ) число орбит G i, вызванных его действием на { 0 , 1 } i (путем перестановки координат). Обозначим через F ( G ) класс языков L, такой что L ∩ { 0 , 1 } n инвариантен относительно G n . Тогда все языки в $G_{i} \leq S_{i}$$s(G_{i})$$G_{i}$$\{0,1\}^{i}$$\mathcal{F}(G)$$L$$L \cap \{0,1\}^{n}$$G_{n}$ есть схемы размера не более р ø л у ( х ( G ) ) и глубиной не более р ø л у ( журнал ( ы ( G ) ) , и это,существужесткой.$\mathcal{F}(G)$$poly(s(G))$$poly(\log(s(G))$

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

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

$PP$$NP$$PP^{PH} \subseteq BP \cdot PP$$BP \cdot PP = PP$$NP$$PP$$PP$$NP$$NP$$PP$

$f$$f(x) = f(y)$$x \sim y$$NP$

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

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