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

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

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

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

• $L = \{ 1^nw \mid w \text{ encodes a satisfiable formula and } |w|=n \}$
• $L = \{ \varphi \mid \varphi \text{ is SAT formula with more than } |\varphi|^2 \text{ satisfying assignments}\}$

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

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

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

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

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

Входные данные: одноленточный TM Вопрос: существует ли n ∈ N , такой, что M делает больше, чем C n + D шагов на некотором входе длины n ?$M$
$n\in\mathbb{N}$$M$$Cn+D$$n$

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

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

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

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

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

Вопрос: существует ли -цветный граф с последовательностью степеней d 1 , … , d n ?$k$$d_1,\ldots,d_n$

Здесь вход может быть описан битами, но свидетель может потребовать Ω ( n 2 ) битов.$O(n\log n)$$\Omega(n^2)$

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

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

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

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

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

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

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

Заметки:

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

2. The natural witness for the original problem is the $n^k$-sized clique, which can be described by an $O(n^{k+1})$ long string (an $n$-bit string for each of the $n^k$ 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)$