Естественные NP-полные проблемы с «большими» свидетелями

28

Вопрос о теории « Что такое NP, ограниченный свидетелями линейного размера? », Задает вопрос о классе NP, ограниченном свидетелями линейного размера , ноO(n)

Существуют ли естественные NP-полные проблемы, в которых (да) экземпляры размера требуют свидетелей размером больше ?нnn

Очевидно, что мы можем построить искусственные проблемы, такие как:

  • L={1nww encodes a satisfiable formula and |w|=n}
  • L={φφ is SAT formula with more than |φ|2 satisfying assignments}

После быстрого взгляда на G & J, каждая естественная проблема NPC, кажется, имеет свидетелей (строго) меньше .n

Есть ли для этого «причина / объяснение»?

Марцио де Биаси
источник
1
Многие проблемы имеют размер свидетеля , например, изоморфизм графов и гамильтонов путь. Вы хотите исключить факторы полилога, или это считается ответом? Θ(nlogn)
Джошуа Грохов
12
На самом деле, размер свидетеля для изоморфизма графа и гамильтоновой траектории можно рассматривать как сублинейный на входе (учитывая, что на входе лежит матрица смежности графа). n×n
Райан Уильямс
1
Ох, верно ...
Джошуа Грохов
1
@MarzioDeBiasi Я думаю, что ваше наблюдение за маленькими свидетелями должно быть использовано для определения естественной NP-полной проблемы.
Мухаммед Аль-Туркистани
1
@MarzioDeBiasi - я согласен, что списка удовлетворительных заданий достаточно, но можете ли вы доказать, что нет более короткого свидетельства проблемы? (возможно, краткий способ представления необходимых заданий).
РБ

Ответы:

10

Как насчет числа раскраски ребер в плотном графе (он же Хроматический индекс )? Вам дана матрица смежности вершинного графа ( n 2- битный ввод), но естественный свидетель, описывающий раскраску, имеет размер n 2 log n . Конечно, в теореме Визинга могут быть более короткие доказательства для графов класса 1 .nn2n2logn

Смотрите также этот возможно связанный вопрос

Андреас Бьёрклунд
источник
2
Кажется, хороший пример! Замечание: проблема NP-полна даже для кубических графов; в этом случае у нас есть свидетель размера битов достаточно (два бита для каждого ребра), что меньше n 2, если мы используем представление матрицы смежности, и я подозреваю, что оно меньше размера экземпляра, какую бы разумную кодировку мы не использовали для кубического графа. 2|E|n2
Марцио Де Биаси
8

Я столкнулся с некоторыми вполне естественными NP-полными проблемами, которые, казалось бы, требуют длинных свидетелей. Проблемы, параметризованные целыми числами и D , следующие:CD

Входные данные: одноленточный TM Вопрос: существует ли n N , такой, что M делает больше, чем C n + D шагов на некотором входе длины n ?M
nNMCn+Dn

Иногда дополнения к проблеме легче сформулировать: выполняется ли данный однотонный TM во время C n + D , т.е. он делает не более C n + D шагов на всех входах размера n , для всех n ?MCn+DCn+Dnn

Полный результат представлен здесь . По сути, показано, что если мы хотим проверить, работает ли однотонная ТМ во время , нам нужно проверить это только на входах длины, ограниченной q O ( C ) , где q - количество состояний ввода ТМ. Таким образом, свидетелем будет ввод длины q O ( C ), для которой ограничение по времени нарушается. В ссылке также показано, что эти задачи NP-полны для всех C 2 и D 1 .Cn+DqO(C)qqO(C)C2D1

Теперь, если свидетель является входом, который нарушает время выполнения, он должен иметь длину в целом. И вход имеет длину O ( q 2 ) .qΩ(C)O(q2)

Дэвид Г
источник
3
Благодарность! Но, честно говоря, я нахожу более «естественной» (я знаю, что это не формальная концепция) проблему: «Учитывая формулу , решите, имеет ли она хотя бы | φ | 2 удовлетворяющих задания» :-)φ|φ|2
Марцио Де Биаси
Я понимаю :). С другой стороны, проблема о имеет длину свидетеля в вопросе, в то время как проблема о ТМ получает длину свидетеля в доказательстве. Более того, длина свидетеля преднамеренно не включена в проблему. φ
Дэвид Г
7

Вот пример, который кажется естественной проблемой.

Экземпляр: целые положительные числа, и k , все ограничены сверху n .d1,,dnkn

Вопрос: существует ли -цветный граф с последовательностью степеней d 1 , , d n ?kd1,,dn

Здесь вход может быть описан битами, но свидетель может потребовать Ω ( n 2 ) битов.O(nlogn)Ω(n2)

Замечание: у меня нет упоминания о том, что эта конкретная проблема действительно является NP-полной. Но требование -цветности может быть заменено любым другим NP-полным условием; проблема, вероятно, станет NP-полной для некоторого условия, если не для этого.k

Андрас Фараго
источник
Для меня эта проблема имеет неправильную структуру, чтобы быть NP-полной, если P = NP. Классы графов, определяемые каждой последовательностью степеней, могут быть очень большими, и многие из них могут иметь окрашиваемых элементов по тривиальной причине. n
Андрас Саламон
@ AndrásSalamon Действительно, я не знаю, какова сложность этой проблемы, или можно ли сделать ее NP-полной, выбрав подходящее условие вместо окрашиваемости. С другой стороны, я был бы удивлен, если бы для каждого проверяемого свойства polytime Q была бы следующая проблема в P : существует ли граф с данной последовательностью степеней, такой, что у этого также есть свойство Q ? kQQ
Андрас Фараго
Я согласен, что кажется маловероятным, что степень степени + свойство всегда находится в P, но, возможно, некоторые из них являются кандидатами в NP-промежуточный статус?
Андрас Саламон
@ AndrásSalamon Да, я могу себе представить, что некоторые из них имеют статус NPI.
Андрас Фараго
6

Может быть, это глупая «причина / объяснение», но для многих задач NP-Complete решение является подмножеством входных данных (рюкзак, покрытие вершины, клика, доминирующий набор, независимый набор, максимальное сокращение, сумма подмножества, ... ) или перестановка или присвоение подмножеству входных данных (гамильтонов путь, коммивояжер, SAT, изоморфизм графов, раскраска графов, ...).

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

усул
источник
Я думаю, что это действительно хорошая «первая идея». Иногда проблемы нельзя классифицировать однозначно. Например, SAT также может быть проблемой подмножества («выберите подмножество истинных переменных»). Или HAMCYCLE - проблема перестановок на вершинах или проблема подмножеств на ребрах? (Кстати, может быть, «проблемы с назначением» действительно могут быть «проблемами с разбиением», скажем, 3-цветным).
Юхо
3

Что касается вашего первого вопроса, Аллендер утверждает (в разделе «Усиление нижних границ с помощью самовосстанавливаемости» ), что ни одна естественная NP-полная проблема, как известно, не лежит за пределами NTIME (n). Это означает, что все известные натуральные NP-комплекты имеют линейные размеры свидетелей.

Мухаммед Аль-Туркистани
источник
1
Обратите внимание, что длина самого длинного принимающего пути в недетерминированной машине Тьюринга соответствует размеру свидетеля.
Мухаммед Аль-Туркистани
1

Рассмотрим следующий вариант задачи MAXCLIQUE .

Экземпляр: схема с 2 n входными битами и полиномиально ограниченного размера в n . Эта схема неявно определяет граф на 2 n вершинах, так что каждая вершина отождествляется с n- битной строкой, а две вершины связаны с ребром, если 2 n- битная строка, полученная путем объединения двух ID вершин, имеет вид принята C . Пусть G ( C ) обозначает этот граф. Обратите внимание , что она имеет экспоненциально много вершин в п , но по - прежнему определяется полиномиальным описанием размеров C .C2nn2nn2nCG(C)nC

Вопрос: содержит ли клику размером n k , где k - фиксированная константа?G(C)nkk

Заметки:

  1. Проблема NP-полная. Содержимое в очевидно. Полноту можно доказать, наблюдая, что если схема принимает только пары вершин, в которых каждый ID не больше N = 2 n k , то G ( C ) может быть произвольным N- вершинным графом плюс много изолированных вершин. (Любой такой N- вершинный граф может быть закодирован в C , поскольку C может иметь полиномиальный размер по n , а значит, и по N ). Тогда возникает вопрос: существует ли N / 2- размерная клика в NNPN=2nkG(C)NNCCnNN/2N-vertex graph? This is known to be NP-complete, for general N. The issue that N is not arbitrary, it is restricted to N=2nk, can be eliminated by appropriate padding.

  2. The natural witness for the original problem is the nk-sized clique, which can be described by an O(nk+1) long string (an n-bit string for each of the nk vertices). Note that k can be a very large constant, so the witness can be much longer than linear. (Even if the input size is the description of C, rather than n, this witness can be still much longer, because k can be chosen independently of C.)

  3. The problem can be viewed as natural, since it is a variant of MAXCLIQUE.

  4. NTIME(n)

Андрас Фараго
источник
Я не уверен, что следую вашему сокращению Half-Clique до этой проблемы, чтобы установить полноту в NP. УчитываяN-vertex instance of Half-Clique, what circuit does it map to?
András Salamon
@AndrásSalamon Let G be an N=2nk-vertex graph, serving as input graph of Half-Clique. Then C is the circuit that accepts any node pair (u,v), if uN,vN (as binary numbers), and (u,v)E(G), otherwise C rejects. (This C can be implemented as a polynomial sized circuit.) Then G(C) will contain G on the first N nodes, plus 2nN additional isolated nodes. The graph G(C) has a clique of size nk precisely when G has a half-clique.
Andras Farago