Простое решение проблемы, сложная проблема поиска

Решить, существует ли равновесие по Нэшу, легко (это всегда так); однако, на самом деле найти его, как полагают, сложно (это PPAD-Complete).

Каковы другие примеры проблем, когда версия решения проста, но поисковая версия относительно сложна (по сравнению с версией решения)?

Я был бы особенно заинтересован в проблемах, где версия решения нетривиальна (в отличие от случая с равновесием Нэша).

Учитывая целое число, есть ли у него нетривиальный фактор? -> Нетривиально в П.

Если задано целое число, найдите нетривиальный множитель, если он есть -> Не известно, что он есть в FP.

Вот еще один пример: для кубического графа G и гамильтонова цикла H в G найти другой гамильтонов цикл в G. Такой цикл существует (по теореме Смита), но, насколько я знаю, он открыт, может ли он быть вычисляется за полиномиальное время.

Если вы дадите следующую ту же «свободу действий», что и для равновесий Нэша, тогда:

• Целочисленная факторизация, где проблема решения - «Есть ли факторизованное представление этого целого числа?» (тривиально, да), и проблема поиска заключается в том, чтобы вывести его

Целый ряд проблем с решеткой, возможно, мог бы здесь соответствовать одному и тому же типу щедрого пособия для определения проблемы решения:

• Проблема кратчайшего вектора (SVP) - решите, есть ли кратчайший вектор против его нахождения
• Проблема ближайшего вектора (CVP) - решите, есть ли ближайший вектор против его нахождения

Конечно, это все случаи, когда версия решения, которую я упомянул, не очень интересна (потому что это тривиально). Одна проблема, которая не так тривиальна :

• окрашиваемость плоского графа для k ≥ $k$$k \ge 4$

Задача решения 4-окрашиваемости плоского графа находится в P. Но получение лексикографически первого такого решения является NP-трудным ( Khuller / Vazirani ).

Обратите внимание, что свойство, которое вас действительно интересует, - это самовосстанавливаемость (или, скорее, несамостоятельность). В задаче раскраски плоского графа существенная проблема заключается в том, что метод саморегуляции общего случая -цветности разрушит планарность графа.$k$

Пусть , случайный граф на 1 , ... , п , в котором каждое ребро присутствует независимо с вероятностью 1 / 2 . Выберите п 1 / 3 вершины из G равномерно случайным образом и добавить все ребра между ними; называть полученный граф H . Тогда Н имеет клику размера п 1 / 3 .$G=G(n,1/2)$$1,\ldots,n$$1/2$$n^{1/3}$$G$$H$$H$$n^{1/3}$

Задача поиска: найти клику размером не менее .$10\log n$

Еще один пример; Subset-сумма равенство: Учитывая 1 , 2 , 3 , . , , , , П натуральных числа с Й п 1 я < 2 п - 1 . Принцип сукна гарантирует существование двух подмножеств I , J в 1 , 2 , . , , , n такое, что ∑ i ∈ I a i =$a_1,a_2,a_3,...,,a_n$$\sum_1^n{a_i} \lt 2^n -1$$I, J$${1,2,..., n}$ (так как большечем подмножества возможных сумм). Существование алгоритма полиномиального времени для нахождения множеств I и J является известной открытой проблемой.$\sum_{i\in I} a_i=\sum_{j \in J} a_j$$I$$J$

Равенство подмножеств-сумм (версия с голубями)

Еще один пример теории чисел, аналогичный приведенным выше. Из постулата Бертрана известно , что для каждого положительного целого числа существует простое число между n и 2 n . Но у нас нет алгоритма полиномиального времени, чтобы найти такое простое число, учитывая n . (Требуемый алгоритм должен выполняться за время polylog ( n ).) Можно легко придумать рандомизированные алгоритмы за полиномиальное время из-за теоремы о простом числе , и можно дерандомизировать их, предполагая некоторые теоретические гипотезы стандартных чисел (такие как гипотеза Крамера).$n$$n$$2n$$n$$n$), но безусловный детерминистический алгоритм за полиномиальное время неизвестен. Соответствующая работа была недавно проделана в проекте Polymath4 ; Сообщение в блоге Дао о проекте - хорошее резюме этого.

Риск быть немного не по теме, позвольте мне привести простой и естественный пример ответа теории C : эйлеровы циклы и распределенные алгоритмы.

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

Тем не менее, существует быстрый и простой распределенный алгоритм, который решает проблему решения (в том смысле, что для экземпляров yes все узлы выводят «1», а для экземпляров no-instance по крайней мере один узел выводит «0»): каждый узел просто проверяет четность своей степени и выводит 0 или 1 соответственно.

Но если вы хотите найти цикл Эйлера (в том смысле, что каждый узел выводит структуру цикла в своей собственной окрестности), то нам нужна существенно глобальная информация на графике. Не должно быть трудно придумать пару примеров, которые показывают, что проблема требует раундов связи; с другой стороны, O ( n ) раундов достаточно для решения любой проблемы (при условии уникальных идентификаторов).$\Omega(n)$$O(n)$

В итоге: -время решения проблемы, Θ ( n ) -время поиска, и это наихудший возможный разрыв.$O(1)$$\Theta(n)$

Редактировать: Это подразумевает, что граф связан (или, что эквивалентно, мы хотим найти эйлеров цикл в каждом связанном компоненте).

Поиск разделов Тверберга неизвестной сложности:

$x_1,x_2,\dots, x_m$$R^d$$m \ge (r-1)(d+1)+1$$S_1,S_2,\dots, S_r$${1,2,\dots,m}$$\cap _{j=1}^r \text{conv} (x_i: i \in S_j) \ne \emptyset$

Как и в случае равновесий по Нэшу, разбиение гарантировано из теоремы, но неизвестно, существует ли алгоритм временного разложения, чтобы найти его.

Гил Калай написал замечательную серию постов на эту тему: Один , Два и Три .

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

$R_1,\ldots,R_k$$\{0,1\}$

$R_1,\ldots,R_k$$R = \{(1,0,0),(0,1,0),(1,1,1)\}$$k = 1$). Как только проблема выполнимости разрешима за полиномиальное время, вопрос о том, существует ли лексикографически минимальное удовлетворяющее присваивание, становится тривиальным.

См. Следствие 13 и пример, следующий за ним в статье выше (по крайней мере, в этой онлайн-версии).

• $k$$k$
• Версия поиска - NP- жесткий: Нахождение хроматического числа графов без индуцированного пути с пятью вершинами; благодаря этой статье .

$e$$e (a + b, c + d) = e (a c) e (a d) e (b c) e (b d)$$e$

$e$$(g, h, g^a, h^b)$$a = b$$e (g, h^b) = e (h, g^a)$

Такие группы также обобщаются на «группы разрыва».

Я думаю, что Planar Perfect Matching пропустили из этого списка.

• $\mathsf{NC}$
• $\mathsf{NC}$

Давайте немного усложним.

Многие проблемы принятия решений о системах сложения векторов (VAS) являются EXPSPACE-полными, но могут потребовать гораздо больших свидетелей. Например, решение о том, является ли язык VAS регулярным, является EXPSPACE-полным (например, Blockelet & Schmitz, 2011 ), но наименьший эквивалентный конечный автомат может иметь размер Аккерманна ( Valk & Vidal-Naquet, 1981 ). Объяснение этого огромного разрыва заключается в том, что существует гораздо меньше свидетелей нерегулярности .