Гипотеза уникальных игр - Unique games conjecture

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

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

Составы

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

Уникальная крышка этикетки

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

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

• 

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

• 

  Решение уникального экземпляра крышки этикетки.

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

• 

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

• 

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

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

Более формально, проблема ( c , s ) -gap label-cover с уникальными ограничениями - это следующая проблема обещания ( L _да , L _нет ):

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

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

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

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

${\ Displaystyle {\ begin {выровненный} x_ {1} & \ Equ 2 \ cdot x_ {2} {\ pmod {7}}, \\ x_ {2} и \ Equ 4 \ cdot x_ {5} {\ pmod {7}}, \\ & {} \ \ \ vdots \\ x_ {1} & \ Equiv 2 \ cdot x_ {7} {\ pmod {7}}. \ End {align}}}$

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

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

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

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

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

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

• L _yes = { G : значение G не менее 1 - δ}
• L _no = { G : значение G не превосходит ε}

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

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

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

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

Гипотеза уникальных игр утверждает, что для каждой достаточно малой пары констант существует такая константа , что каждая задача в NP имеет вероятностно проверяемое доказательство над алфавитом размера с полнотой , надежностью и сложностью случайности, что является уникальной игрой. ${\ displaystyle \ varepsilon, \ delta> 0}$${\ displaystyle K}$${\ displaystyle K}$${\ displaystyle 1- \ delta}$${\ displaystyle \ varepsilon}$${\ Displaystyle О (\ журнал п)}$

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

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

Проблема	Poly.-time ок.	Твердость NP	Твердость UG
Макс 2SAT	${\ displaystyle 0.940 \ dots}$	${\ Displaystyle 0.954 \ точки + \ varepsilon}$	${\ Displaystyle 0.9439 \ точки + \ varepsilon}$
Максимальный разрез	${\ displaystyle 0,878 ... \ точки}$	${\ displaystyle {\ tfrac {16} {17}} + \ varepsilon \ приблизительно 0,941}$	${\ Displaystyle 0.878 \ точки + \ varepsilon}$
Минимальное покрытие вершины	${\ displaystyle 2}$	${\ displaystyle 1.360 \ dots - \ varepsilon}$	${\ displaystyle 2- \ varepsilon}$
Дуга обратной связи установлена	${\ Displaystyle О (\ журнал п \ журнал \ журнал п)}$	${\ displaystyle 1.360 \ dots - \ varepsilon}$	Все константы
Максимальный ациклический подграф	${\ displaystyle {\ tfrac {1} {2}} + \ Omega (1 / {\ sqrt {\ Delta}})}$	${\ displaystyle {\ tfrac {65} {66}}}$	${\ displaystyle {\ tfrac {1} {2}} + \ varepsilon}$
Близость	${\ displaystyle {\ tfrac {1} {3}}}$	${\ displaystyle {\ tfrac {47} {48}}}$	${\ displaystyle {\ tfrac {1} {3}} + \ varepsilon}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

использованная литература

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