Нетривиальное членство в НП

Есть ли пример языка, который есть в , но где мы не можем доказать этот факт непосредственно, показывая, что существует полиномиальное свидетельство о членстве в этом языке?$NP$

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

В более общем плане, есть ли интересные примеры проблем в так что трудно увидеть, что они есть в ?$NP$$NP$

Полу-ответом будет проблема определения победителя в паритетных играх: чтобы показать, что он находится в (даже ), нам нужна теорема о позиционной определенности, которая является глубокой и нетривиальной. Однако этот ответ не идеален, поскольку он все еще сводится к существованию полиномиального свидетеля для этой точной проблемы (позиционной стратегии) ​​и не сводится к другой другой проблеме.$NP$$NP\cap coNP$$NP$

Другим из них может быть алгоритм простоты AKS: решение, является ли число простым, является полиномиальным, в то время как для этого факта есть немало свидетельств. Допустим, мы исключаем «удивительные полиномиальные алгоритмы», поскольку многие из них соответствуют описанию выше. Меня больше интересуют удивительные алгоритмы , которые не являются детерминированными.$NP$

Целочисленное программирование .

Показано, что если существует целочисленное решение, то существует целочисленное решение полиномиального размера. Видеть

• Христос Пападимитриу, « О сложности целочисленного программирования », JACM, 1981.

В то время как проблема "является ли число пересечений графа не более ?" тривиально в NP, NP-принадлежность связанных задач для прямолинейного числа пересечений и числа пересечений пар весьма неочевидна; ср Bienstock, Некоторые, вероятно, сложные проблемы с пересекающимися числами, Discrete Comput. Geometry 6 (1991) 443-459 и Schaefer et al., Распознавание графов струн в NP, J. Comput. System Sci. 67 (2003) 365-380.$k$

Мой любимый пример - классический результат Ашока Чандры и Филиппа Мерлина 1977 года . Они показали, что проблема удержания запросов разрешима для конъюнктивных запросов. Проблема удержания конъюнктивного запроса оказывается эквивалентной решению, существует ли гомоморфизм между двумя входными запросами. Это перефразирует проблему семантики, включающую квантификацию по бесконечному множеству, в синтаксическую, требующую проверки лишь конечного числа возможных гомоморфизмов. Сертификат гомоморфизма имеет только линейный размер, поэтому проблема в NP.

Эта теорема обеспечивает одну из основ теории оптимизации запросов к базе данных. Идея состоит в том, чтобы преобразовать запрос в другой, более быстрый. Однако требуется уверенность в том, что процесс оптимизации не создает новый запрос, который не дает ответов в некоторых базах данных, в которых исходный запрос действительно дал результаты.

Формально запрос к базе данных - это выражение в форме , где - список свободных переменных, является списком связанных переменных, а является формулой первого порядка с переменными и языка с символами отношения. Запрос может содержать экзистенциальные и универсальные квантификаторы, формула может содержать конъюнкцию и дизъюнкцию реляционных атомов, а также может появляться отрицание. Запрос применяется к экземпляру базы данных , который представляет собой набор отношений. Результатом является набор кортежей; когда кортеж$\mathbf{x}.Q(\mathbf{x},\mathbf{y})$$\mathbf{x}$$\mathbf{y}$$Q(\mathbf{x},\mathbf{y})$$\mathbf{x}$$\mathbf{y}$$Q$$I$$\mathbf{t}$ в результате заменяется на тогда формула может быть удовлетворена. Затем можно сравнить два запроса: содержится в если всякий раз, когда применяется к произвольному экземпляру базы данных, выдаю некоторые результаты, тогда применяемый к тому же экземпляру, также выдаю некоторые результаты. (Это нормально, если не приводит к результатам, но дает, но для сдерживания импликация должна выполняться для каждого возможного экземпляра.) Проблема запроса запроса задается: с учетом двух запросов к базе данных$\mathbf{x}$$Q(\mathbf{t},\mathbf{y})$$Q_1$$Q_2$$Q_1$$I$$Q_2$$I$$Q_1$$Q_2$$Q_1$и , содержится ли в ?$Q_2$$Q_1$$Q_2$

До Чандра-Мерлина было не совсем ясно, что проблема разрешима. Используя только определение, нужно количественно определить бесконечный набор всех возможных баз данных. Если запросы не ограничены, то проблема, по сути, неразрешима: пусть будет формулой, которая всегда верна, тогда содержится в если допустимо. (Это проблема Гильберта Entscheidungs , показанная неразрешимой Церковью и Тьюрингом в 1936 году.)$Q_1$$Q_1$$Q_2$$Q_2$

Чтобы избежать неразрешимости, конъюнктивный запрос имеет довольно ограниченную форму: содержит только экзистенциальные квантификаторы, а отрицание и дизъюнкция недопустимы. Таким образом, является положительной экзистенциальной формулой только с соединением реляционных атомов. Это небольшой фрагмент логики, но этого достаточно, чтобы выразить большую часть полезных запросов к базе данных. Классический оператор в SQL выражает конъюнктивные запросы; большинство запросов поисковых систем являются конъюнктивными запросами.$Q$$Q$SELECT ... FROM

Можно определить гомоморфизмы между запросами простым способом (аналогично гомоморфизму графа с небольшим дополнительным учетом). Теорема Чандра-Мерлина гласит: учитывая два конъюнктивных запроса и , содержится в если существует гомоморфизм запросов от к . Это устанавливает членство в NP, и легко показать, что это также NP-сложный.$Q_1$$Q_2$$Q_1$$Q_2$$Q_2$$Q_1$

• Ашок К. Чандра и Филипп М. Мерлин, Оптимальная реализация конъюнктивных запросов в реляционных базах данных , STOC '77 77–90. doi: 10.1145 / 800105.803397

Разрешимость содержания запроса была позже распространена на объединения конъюнктивных запросов (экзистенциальные положительные запросы, где разрешена дизъюнкция), хотя разрешение дизъюнкции повышает сложность до -complete. Результаты разрешимости и неразрешимости также были установлены для более общей формы содержания запроса , включающей оценки полукольца, которые возникают при подсчете количества ответов, при объединении аннотаций в происхождении или при объединении результатов запросов в вероятностных базах данных.$\Pi^P_2$

Я нашел хорошего кандидата, читая некоторые статьи о квадратичных диофантовых уравнениях:

JC Lagarias, сжатые сертификаты для решений бинарных квадратичных диофантовых уравнений (2006)

Из аннотации: ... Пусть обозначает длину двоичного кодирования двоичного квадратичного диофантова уравнения заданного , Предположим, что такое уравнение, имеющее неотрицательное целочисленное решение. Эта статья показывает, что существует доказательство (т. Е. «Сертификат»), что имеет такое решение, которое можно проверить в бите операции. Следствием этого результата является то, что множество находится в классе сложности NP ...$L(F)$$F$$a x_1^2 +b x_1 x_2+ c x_2^2 +d x_1+e x_2 + f = 0$$F$$F$$O(L(F)^5 \log L(F) \log \log L(F))$$\Sigma = \{F : F \text{ has a nonnegative integer solution}\}$

... но, честно говоря, единственным доказательством того, что оно нетривиально, является количество страниц в газете ... 62! :-)

Когда распознавание графа допуска было открыто, следующий документ показал, что он находится в NP:

http://www.sciencedirect.com/science/article/pii/S0166218X04000940

(Позже было показано, что распознавание графа допусков завершено NP: http://arxiv.org/abs/1001.3251 )

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

• Кристоф Хааз, Стефан Кройцер, Жоэль Уакнин, Джеймс Уоррелл, Достижимость в лаконичных и параметрических автоматах с одним счетчиком , CONCUR 2009, LNCS 5710 369–383. doi: 10.1007 / 978-3-642-04081-8_25 ( расширенная версия )

Вот пример (хотя и по общему признанию искусственный), когда очень трудно решить, есть ли проблема в или нет. Пусть - два языка, с , и . Теперь определим язык следующим образом:$NP$$L_1, L_2$$L_1\in NP$$L_2\notin NP$$L$

Тогда точно, если гипотеза двойного простого числа верна. Поскольку гипотеза либо верна, либо нет, она действительно хорошо определена, является ли или нет. Однако, решение, которое имеет место, то есть решение о членстве в , равносильно решению знаменитой гипотезы о двойном простом числе, так что это, конечно, нетривиально ...$L\in NP$$L\in NP$$NP$