Гипотеза об уникальных играх

Нерешенная задача в информатике :

Верна ли гипотеза уникальных игр?

(еще нерешенные проблемы по информатике)

В теории сложности вычислений гипотеза уникальных игр (часто называемая UGC ) — это гипотеза, выдвинутая Субхашем Хотом в 2002 году. Гипотеза постулирует, что задача определения приблизительного значения игры определенного типа, известной как уникальная игра , имеет NP-трудную вычислительную сложность . Оно имеет широкие применения в теории жесткости приближения . Если гипотеза об уникальных играх верна и P ≠ NP, тогда для многих важных задач не только невозможно получить точное решение за полиномиальное время (как постулируется проблемой P и NP ), но также невозможно получить хорошее приближение за полиномиальное время. Проблемы, для которых справедлив такой результат о неаппроксимируемости, включают проблемы удовлетворения ограничений , которые возникают в самых разных дисциплинах.

Гипотеза необычна тем, что академический мир, похоже, разделился примерно поровну во мнениях, верна она или нет.

Составы

Гипотезу об уникальных играх можно сформулировать множеством эквивалентных способов.

Уникальная обложка для этикетки

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

Это означает, что экземпляр покрытия меток с уникальными ограничениями в алфавите размера k может быть представлен как ориентированный граф вместе с набором перестановок π _e : [ k ] → [ k ], по одной для каждого ребра e графа. Присвоение экземпляру покрытия метки присваивает каждой вершине G значение из набора [ k ] = {1, 2, ... k}, часто называемое «цветами».

• 
  Экземпляр уникальной обложки-этикетки. Четырем вершинам можно присвоить красный, синий и зеленый цвета, при этом удовлетворяя ограничениям на каждом ребре.
• 
  Решение проблемы уникального экземпляра обложки этикетки.

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

• 
  Экземпляр уникальной обложки метки, которая не позволяет выполнить удовлетворительное назначение.
• 
  Назначение, удовлетворяющее всем ребрам, кроме толстого. Таким образом, этот экземпляр имеет значение 3/4.

Значение уникального экземпляра покрытия метки — это доля ограничений, которой может удовлетворить любое присвоение. Для выполнимых примеров это значение равно 1, и его легко найти. С другой стороны, определить ценность невыполнимой игры, кажется, очень сложно, даже приблизительно. Гипотеза об уникальных играх формализует эту трудность.

Более формально, проблема покрытия метками ( c , s )-пробела с уникальными ограничениями представляет собой следующую проблему обещаний ( L _yes , L _no ):

• L _да = { G : Некоторое присваивание удовлетворяет хотя бы c -доли ограничений в G }
• L _no = { G : Каждое присваивание удовлетворяет не более s -доли ограничений в G }

где G — это пример проблемы покрытия меток с уникальными ограничениями.

Гипотеза об уникальных играх утверждает, что для каждой достаточно малой пары констант ε , δ > 0 существует константа k такая, что (1 − δ , ε задача покрытия метками )-пробелов с уникальными ограничениями над алфавитом размера k равна NP -жесткий .

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

${\begin{aligned}x_{1}&\equiv 2\cdot x_{2}{\pmod {7}},\\x_{2}&\equiv 4\cdot x_{5}{\pmod {7}},\\&{}\ \ \vdots \\x_{1}&\equiv 2\cdot x_{7}{\pmod {7}}.\end{aligned}}$

Это пример проблемы покрытия меток с уникальными ограничениями. Например, первое уравнение соответствует перестановке π _{(1, 2),} где π _{(1, 2)} ( x ₁ ) = 2 x ₂ по модулю 7.

Системы доказательства с двумя пруверами

Уникальная игра — это частный случай игры с двумя доказывающими и одним раундом (2P1R) . В игре с двумя пруверами и одним раундом участвуют два игрока (также известные как пруверы) и судья. Судья отправляет каждому игроку вопрос, составленный на основе известного распределения вероятностей , и каждый игрок должен отправить ответ. Ответы поступают из набора фиксированного размера. Игра задается предикатом, который зависит от вопросов, отправленных игрокам, и полученных ими ответов.

Игроки могут заранее выбрать стратегию, но не могут общаться друг с другом во время игры. Игроки выигрывают, если предикат удовлетворен их вопросами и ответами.

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

Гипотеза об уникальных играх утверждает, что для каждой достаточно малой пары констант ε , δ > 0 существует константа k такая, что следующая проблема обещания ( L _yes , L _no ) является NP-трудной :

• L _да = { G : значение G не менее 1 − δ}
• L _no = { G : значение G не превышает ε}

где G — уникальная игра, ответы которой берутся из множества размера k .

Вероятностно проверяемые доказательства

Альтернативно, гипотеза об уникальных играх постулирует существование определенного типа вероятностно проверяемого доказательства для проблем в NP.

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

Гипотеза единственных игр утверждает, что для любой достаточно малой пары констант $\varepsilon ,\delta >0$ есть константа $K$ такой, что каждая проблема в NP имеет вероятностно проверяемое доказательство в алфавите размера $K$ с полнотой $1-\delta$, надежность $\varepsilon$и сложность случайности $O(\log n)$ это уникальная игра.

Актуальность

Результаты аппроксимации при условии, что P ≠ NP по сравнению с UGC.

Проблема	Поли.-время ок.	Твердость НП	И твердость
Макс 2САТ	$0.940\dots$	$0.954\dots +\varepsilon$	$0.940\dots +\varepsilon$
Макс. разрез	$0.878...\dots$	${\tfrac {16}{17}}+\varepsilon \approx 0.941$	$0.878\dots +\varepsilon$
Минимальное покрытие вершин	$2$	${\sqrt {2}}-\varepsilon$	$2-\varepsilon$
Набор дуг обратной связи	$O(\log n\log \log n)$	$1.360\dots -\varepsilon$	Все константы
Максимальный ациклический подграф	${\tfrac {1}{2}}+\Omega (1/{\sqrt {\Delta }})$	${\tfrac {65}{66}}$	${\tfrac {1}{2}}+\varepsilon$
Посредничество	${\tfrac {1}{3}}$	${\tfrac {47}{48}}$	${\tfrac {1}{3}}+\varepsilon$

Некоторые очень естественные, по своей сути интересные утверждения о таких вещах, как голосование и пена, просто вылезли из изучения пользовательского контента... Даже если пользовательский контент окажется ложным, он вдохновил на множество интересных математических исследований.

— Райан О'Доннелл ,

Гипотеза об уникальных играх была выдвинута Субхашем Хотом в 2002 году для достижения прогресса в некоторых вопросах теории трудности приближения .

Справедливость гипотезы об уникальных играх предполагает оптимальность многих известных аппроксимационных алгоритмов (при условии, что P ≠ NP). Например, коэффициент аппроксимации, достигаемый алгоритмом Гоеманса и Уильямсона для аппроксимации максимального разреза графа , оптимален с точностью до любой аддитивной константы при условии гипотезы об уникальных играх и P ≠ NP.

Список результатов, которые, как известно, следует из гипотезы об уникальных играх, показан в соседней таблице вместе с соответствующими лучшими результатами для более слабого предположения P ≠ NP. Константа $c+\varepsilon$ или $c-\varepsilon$ означает, что результат справедлив для каждой константы (относительно размера задачи), строго большей или меньшей $c$, соответственно.

Обсуждение и альтернативы

В настоящее время нет единого мнения относительно истинности гипотезы об уникальных играх. Некоторые более сильные формы гипотезы были опровергнуты.

Другая форма гипотезы постулирует, что выделение случая, когда ценность уникальной игры не менее $1-\delta$ из случая, когда значение не более $\varepsilon$ невозможно для алгоритмов с полиномиальным временем (но, возможно, не NP-трудных). Эта форма гипотезы по-прежнему будет полезна для приложений, связанных с трудностями аппроксимации.

Константа $\delta >0$ в приведенных выше формулировках гипотеза необходима, если только P = NP. Если требование единственности удалено, соответствующее утверждение, как известно, верно по теореме о параллельном повторении , даже если $\delta =0$.

Марек Карпински и Уоррен Шуди построили схемы аппроксимации с линейным временем для плотных экземпляров задачи об уникальных играх.

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

В 2010 году Прасад Рагхавендра и Дэвид Стерер определили проблему расширения малых множеств и предположили, что она NP-трудна . Из этой гипотезы следует гипотеза единственных игр. Он также использовался для доказательства строгости результатов аппроксимации при нахождении полных двудольных подграфов .

В 2010 году Санджив Арора , Боаз Барак и Дэвид Стерер нашли алгоритм субэкспоненциальной аппроксимации по времени для задачи уникальных игр.

В 2012 году было показано, что выделение экземпляров со значением не более ${\tfrac {3}{8}}+\delta$ из экземпляров со значением не менее ${\tfrac {1}{2}}$ является NP-трудным.

В 2018 году после серии статей была доказана более слабая версия гипотезы, названная гипотезой 2-2 игр. В определенном смысле это доказывает «половину» исходной гипотезы. Это также устраняет самый известный пробел в уникальной обложке этикетки: NP-трудно отличить экземпляры с максимальной ценностью. $\delta$ из экземпляров со значением не менее ${\tfrac {1}{2}}$.

Ссылки

• Хот, Субхаш (2010), «О гипотезе уникальных игр», Proc. 25-я конференция IEEE по сложности вычислений (PDF) , стр. 99–121, doi : 10.1109/CCC.2010.19 .