Скачки твердости в вычислительной сложности?

Проблема минимальной пропускной способности состоит в том, чтобы найти порядок узлов графа на целочисленной линии, который минимизирует наибольшее расстояние между любыми двумя соседними узлами. -caterpillar дерево формируется из основного пути, выращивая реберно непересекающихся путей длины не более из его узлов ( называется длиной волос). Проблема минимальной полосы пропускания в для 2-гусениц, но полная для 3-гусениц.$k$$k$$k$$P$$NP$

Вот очень интересный факт: проблема минимальной полосы пропускания разрешима за полиномиальное время для 1-гусениц (длина волос не более одной), но она является полной для циклических 1-гусениц (в циклической гусенице для соединения конечных точек добавлен один край основного пути). Таким образом, добавление ровно одного ребра делает задачу полной.$NP$$NP$

Что является наиболее ярким примером скачка твердости задачи, когда небольшая вариация входного экземпляра вызывает переход сложности от разрешимости за полиномиальное время к полноте?$NP$

Один из наиболее интересных прикладных примеров скачков твердости можно наблюдать в следующей задаче:

Рассмотрим чемпионат футбольной лиги с командами. Проблема определения, может ли данная команда (все еще) выиграть лигу, находится в если в матче победившая команда получает 2 очка, проигравший 0 и каждая команда получает 1 очко в ничейном матче Но если мы изменим правила, чтобы победившая команда получила 3 ​​очка, та же проблема становится трудной.P N $n$$P$$NP$

Результат может быть обобщен для любого -точечного правила для каждого и даже только для трех оставшихся раундов.k > $(0, 1, k)$$k > 2$

Источник: «Теория сложности» Инго Вегенера ( http://portal.acm.org/citation.cfm?id=1076319 )

Это отвечает на вопрос, заданный в названии вопроса, но не тот, который задан в вопросе.

Шокирующий пример скачка твердости возникает из вопроса: «Сколько удовлетворительных заданий имеет плоская формула по модулю ?» Считалось, что это # ​​P-hard, и это для «большинства» значений , но если - целое число Мерсенна (например, , потому что 7 имеет форму ), то Ответ может быть вычислен за полиномиальное время.n n n = 7 2 3 - $n$$n$$n$$n=7$$2^3-1$

Впервые он был обнаружен Валиантом в своей революционной статье «Голографические алгоритмы».

НЕЗАВИСИМАЯ SET является NP-полной для (креста, треугольник) -свободных графиков , но может быть решена в линейное время (стул, треугольник) -свободные графы . (Графы без X - это графы, которые не содержат граф из X в качестве индуцированного подграфа.)

стул: треугольник: крестик

Обратите внимание, что крест получается от стула путем добавления одного ребра.

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

Вот пример проблемы, которая демонстрирует резкую дихотомию по предложенным вами направлениям.

Задача определения того, существует ли гомоморфизм графов из входного графа G в фиксированный шаблонный граф H, находится в P, когда H является графом с сам циклом или двудольным графом без петель. Когда H не является двудольным (это часто может быть достигнуто путем добавления одного ребра), тогда проблема становится NP-полной.

• P. Hell и J. Nešetřil, Сложность H-окраски , J. Comb. Th. B 48 92–110, 1990. doi: 10.1016 / 0095-8956 (90) 90132-J

Ключевым моментом здесь является то, что 2-раскраска находится в P (это соответствует гомоморфизму в , пути на 3 вершинах), тогда как 3-раскраска является NP-полной (это соответствует гомоморфизму в , треугольник).K $P_3$$K_3$

Вот еще один интересный пример, связанный с обнаружением подграфа:

Тета представляет собой график с несмежными вершинами , трех путей от до , где любые два путей индуцированного цикла с длиной больше 3.$x,y$$P_1, P_2, P_3$$x$$y$

Пирамида представляет собой график с вершиной , треугольник и путем от до для каждого , с не более чем один путем с длиной одной.$x$$y_1,y_2,y_3$$P_i$$x$$y_i$$i=1,2,3$

Наконец, призма - это граф с двумя треугольниками и и путями от до для каждого .$x_1,x_2,x_3$$y_1,y_2,y_3$$P_i$$x_i$$y_i$$i=1,2,3$

Это легко описать цифрами:

Известно, что для обнаружения индуцированной тэты и пирамиды это происходит за полиномиальное время. (На самом деле, самый известный алгоритм для тэты занимает времени, а для пирамиды - .) Но для обнаружения наведенной призмы задача становится NP-трудной.$O(n^{11})$$O(n^9)$

Можно посмотреть « Обнаружение индуцированных подграфов » Левека, Лина, Маффрея и Тротиньона для справки. Причина, по которой тэта и пирамида относительно просты, связана с проблемой «три в дереве», описанной в « Задаче три в дереве » Чудновского и Сеймура.

э-э ... я уверен, что вы ищете менее тривиальные примеры ... но я хотел бы отметить, что есть что-то особенное в числе против . до , против и т. Д. Интуитивно я всегда полагал, что это происходит потому, что узел, имеющий не более 2 ребер, может образовывать не более одной линии, а узел с 3 ребрами - дерево, когда мы переходим от 2-3, мы получаем комбинаторный взрыв.3 2 - S A T 3 - S A T 2 - C O L 3 - C O $2$$3$$2-SAT$$3-SAT$$2-COL$$3-COL$

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

Мы можем рассмотреть параметризованное семейство распределений, а затем поговорить о том, что происходит, когда мы меняем параметр. Возможно, вас заинтересует то, что называется пороговым явлением , «когда система претерпевает быстрые качественные изменения в результате небольшого изменения параметра ...». Взгляните на этот обзор: Эхуд Фридгут , « Охота за острыми порогами », Алгоритмы случайных структур, 26, 2005.

Я думаю, что один из самых ярких и красивых примеров - это случайный k-SAT с плотностью предложения , фазовый переход действительно потрясающий.$\Delta$

Выведение типов терминов лямбды-DEXPTIME в комплекте с предваренным и рангом-2 системами полиморфного типа (когда кванторы типа вложены более одного глубокого уровня), но становится неразрешимым для ранга-3 и выше. Странно, что один дополнительный уровень вложенности может сделать проблему неразрешимой.

Нахождение основного состояния плоской модели Изинга с нулевым магнитным полем в P, с ненулевым магнитным полем - NP-трудное. Функция разбиения плоской модели Изинга с 0 магнитным полем находится в P, с ненулевым магнитным полем - NP-жесткая.

Вот хорошая проблема с интересным переходом сложности, как минимальная пропускная способность, которую вы указали в своем вопросе.

Пусть граф и остовного дерева . Крюк для краевой является единственным путь в . Перегрузка , обозначаемая является количеством обходных путей, содержащих . Скопление в , обозначается , максимальная загруженность по всем ребрам в . Перегрузка связующего дерева группы , обозначаемая $G$$T$$G$$uv\in E(G)$$u$$v$$T$$e \in E(T)$$\mathrm{cng}_{G,T}(e)$$e$$G$$T$$\mathrm{cng}_G(T)$$T$$G$$\mathrm{stc}(G)$, Минимальная загруженность по всем остовных деревьев . Проблема перегруженности связующего дерева спрашивает, имеет ли данный граф перегруженность связующего дерева не более некоторого заданного .$G$$k$

Следующий скачок сложности показан в: Bodlaender et al., Параметризованная сложность проблемы перегруженности связующего дерева , Algorithmica 64 (2012) 85–111 :

Для каждого фиксированного и задача разрешима за линейное время для графиков степени не более . Напротив, если мы допустим только одну вершину неограниченной степени, задача сразу становится -полной для любого фиксированного .d d N P k ≥ $k$$d$$d$$\mathsf{NP}$$k\ge 8$

Интересно, почему никто не упомянул это:

Хорн-Сат против К-Сат

Я думаю, что все знают, что это такое. Если не:

Horn-Sat должен определить, является ли набор клаузл рога выполнимым (каждое предложение имеет не более 1 положительного литерала).

K-Sat должен определить, является ли набор предложений выполнимым (каждое предложение может иметь более 1 положительного литерала).

Таким образом, использование более одного положительного литерала в каждом предложении делает проблему из P-полной NP-полной.

Раскраска графика

Как уже упоминалось в другом ответе, 2-COL разрешима за полиномиальное время, в то время как 3-COL является NP-полной. Но при увеличении количества цветов после некоторого (неизвестного?) Момента проблема становится легче!

Например, если у нас есть N вершин и N цветов, проблему можно решить, назначив разные цвета каждой вершине.

В том же духе: постоянный против детерминанта.

Я только что прочитал статью, посвященную разделению гиперграфа . Проблема определяется так, цитата:

$k$$l$$1 \leq l < k$$P^l_k$$\mathcal{H} = (V, \mathcal{E})$$t_1, \dots, t_k$$|V| = n = \sum^k_{i=1} t_i$$|\mathcal{E}| = m$$V$$k$$t_1, \dots, t_k$$\mathcal{E}$$l$

В целом доказано, что:

• $P^1_k$$n,m$$k \geq 2$
• $P^l_k$$2 \leq l < k$

Если этого недостаточно, прыгайте дальше. Для гиперграфов с непересекающимися гиперэгезиями показано:

• $P^1_k$$k \geq 2$
• $P^l_k$$m$$2 \leq l < k$

Лоран Люоде. 2010. NP-жесткий и линейный варианты разбиения гиперграфа. Теор. Вычи. Sci. 411, 1 (январь 2010), 10-21. http://dx.doi.org/10.1016/j.tcs.2009.08.035

Интересные скачки сложности известны проблемой планирования работы магазина.

$n$$M$$m$$j$$\mu_j$$O_{1j},O_{2j},\dots,O_{\mu_jj}$$O_{ij}$$p_{ij}$$m_{ij}\in M$$C_j$$j$

$C_{max}=max_jC_j$$\sum C_j$

$J||\gamma$$\gamma$

$J2|n=k|F$$J|n=2|F$$J2$ $(n=k)$$2$ $(k)$$F$

$J3|n=3|C_{max}$$J3|n=3|\sum C$

$J2||C_{max}$$J2||\sum C$

Таким образом, здесь мы видим, что происходит скачок, когда мы переходим с двух рабочих мест / машин на три.

Во многих случаях приближенные задачи NP-оптимизации приводят к резким скачкам сложности. Например, SET COVER может быть аппроксимирована с коэффициентом за полиномиальное время (по алгоритму Жадности), но NP-сложная аппроксимация с коэффициентом .$\ln n$$(1-o(1))\ln n$

$2^n$$2^n$$(a+b)^n=\sum_{i\in{0..n}}{{n}\choose{i}}a^ib^{n-i}$$p_b(a)$$a=b=1$$2^n=p_1(1)$как сумма. Теперь предположим, что у вас есть матрица проблем с производительностью по двум переменным, пропорциональным биномиальным коэффициентам (по сравнению с размером задачи, описываемым двумя переменными), расположенным в виде паскальского треугольника. Тогда решение всех проблем в n-й строке должно занять . Биномиальные коэффициенты описывают, сколько существует различных способов выбора k-комбинаций из n элементов. Таким образом, если ваш алгоритм зависит от перечисления k-комбинаций из n элементов алгоритм не может быть полиномиальным временем. Поскольку, если эта проблема была полиномиальным временем, то приведенный выше аргумент доказывает , так как сумма двух полиномов является полиномом. Но правильные доказательства проблемы любом случае редки.$DTIME(2^n)$$(k<n)$$P=NP=DTIME(2^n)$$P=NP$