NP-полные проблемы не «очевидно» в NP

27

Многим пришло в голову, что во всех $\textbf{NP}$ полных доказательствах, которые я читал (которые я помню), всегда тривиально показать, что проблема в $\textbf{NP}$ , и показать, что это $\textbf{NP}$ жесткая, является ... трудной частью , Какие $\textbf{NP}$ полные проблемы это те, чьи верификаторы за полиномиальное время весьма нетривиальны?

complexity-theory np-complete np gardenhead
источник

9

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

Шалл

2

Доказать, что «ПРАЙМ» находится в NP, было определенно намного сложнее, чем доказать, что большинство NP-завершенных проблем находятся в NP.

gnasher729

1

Смотрите также более общий вопрос cstheory.stackexchange.com/q/21106/109 на CS.SE.

Андрас Саламон

19

Существует по крайней мере четыре таких неполных перечисленных проблемы, перечисленных в приложении к ГЭРИ и Джонсону « КОМПЬЮТЕРЫ И ИНТРАКТИВНОСТЬ»: Руководство по теории NP-полноты . $NP$

[AN6] Неделимость продукта полинома

Экземпляр: Последовательности пар целых чисел, причем каждый и целое число . $A_i = \langle (a_i[1],b_i[1]), ..., (a_i[k],b_i[k]) \rangle,\ 1 \leqslant i \leqslant m,$ $b_i[j] \geqslant 0,$ $N$

ВОПРОС: Разве не делится на ? $\displaystyle \prod_{i=1}^m \left( \displaystyle\sum_{j=1}^k a_i[j] \cdot z^{b_i[j]} \right)$ $z^N - 1$

Ссылка: [Плейстед, 1977а] , [Плейстед, 1977b] . Преобразование из 3SAT. Доказательство членства в НП нетривиально и фигурирует во второй ссылке.

Другие три, которые я нашел в приложении:

[LO13] МОДАЛЬНАЯ ЛОГИКА S5-СООТВЕТСТВИЕ
[LO19] ВТОРОЙ ЗАКАЗ УСТАНОВКИ
[MS3] НЕДОСТАТОЧНОСТЬ БЕСПЛАТНОГО ВЫБОРА СЕТЕЙ ПЕТРИ

Кайл Джонс
источник

Благодарность! У меня есть эта книга, поэтому я обязательно проверю их.

садовник

Я немного неясен относительно этой проблемы: (1) Правильно ли я интерпретирую z - переменную, которая может принимать любое целочисленное значение (как обычное линейное / квадратное уравнение). (2) Таким образом, неделимость будет эквивалентна заявлению о том, что: «ни для какого целого значения z уравнение A не делится на B»?

TheoryQuest1

1

Из анализа первых двух страниц статьи 1977 года я понял, что

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

z

$z$

Кайл Джонс

4

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

В Serializability by Locking (Страница 237) это говорит о том, что

Что касается сложности безопасности, Papadimitriou et al. [14] показали, что трудно проверить, является ли система транзакций -безопасной, и предположили, что проблема в . Из теоремы 3 (в этой статье) следует, что это верно. $\textrm{NP}$ $SSR$ $\textrm{NP}$

Проблема безопасности может быть найдена в статье Papadimitriou et al. "Некоторые вычислительные проблемы, связанные с управлением параллелизмом баз данных". К сожалению, у меня нет доступа к нему. $SSR$

Hengxin
источник

2

Для меня в этом классе целочисленное линейное программирование (и связанная с ним квантификатор без арифметики пресбургера).

Наивным подходом к мерной задаче ILP является итерация по всем длинам векторов целых чисел. Но это неограниченный процесс. $n$ $n$

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

Больше информации можно найти в ответе на вопрос, который я задал некоторое время назад.

jmite
источник

NP-полные проблемы не «очевидно» в NP

Ответы: