Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Нерешенная проблема в информатике :

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

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

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

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

Составы [ править ]

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

Уникальная обложка лейбла [ править ]

Следующая формулировка гипотезы об уникальных играх часто используется для трудностей приближения . Гипотеза постулирует 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:

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

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

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

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

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

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

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

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

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

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

A unique game can be viewed as a special kind of nonadaptive probabilistically checkable proof with query complexity 2, where for each pair of possible queries of the verifier and each possible answer to the first query, there is exactly one possible answer to the second query that makes the verifier accept, and vice versa.

The unique games conjecture states that for every sufficiently small pair of constants ε, δ > 0 there is a constant K such that every problem in NP has a probabilistically checkable proof over an alphabet of size K with completeness 1 − δ, soundness ε and randomness complexity O(log(n)) which is a unique game.

Relevance[edit]

Approximability results assuming P ≠ NP versus the UGC
ProblemPoly.-time approx.NP hardnessUG hardness
Max 2-Sat0.940...[5]0.954... + ε[6]0.9439... + ε[7]
Max Cut0.878...[8]0.941... + ε[6]0.878... + ε[7]
Min Vertex Cover21.360... − ε[9]2-ε[10]
Betweenness1/347/48[11]1/3 + ε[12]

Some very natural, intrinsically interesting statements about things like voting and foams just popped out of studying the UGC.... Even if the UGC turns out to be false, it has inspired a lot of interesting math research.

— Ryan O’Donnell, [1]

The unique games conjecture was introduced by Subhash Khot in 2002 in order to make progress on certain questions in the theory of hardness of approximation.

The truth of the unique games conjecture would imply the optimality of many known approximation algorithms (assuming P ≠ NP). For example, the approximation ratio achieved by the algorithm of Goemans and Williamson for approximating the maximum cut in a graph is optimal to within any additive constant assuming the unique games conjecture and P ≠ NP.

A list of results that the unique games conjecture is known to imply is shown in the adjacent table together with the corresponding best results for the weaker assumption P ≠ NP. A constant of c + ε or c − ε means that the result holds for every constant (with respect to the problem size) strictly greater than or less than c, respectively.

Discussion and alternatives[edit]

Currently, there is no consensus regarding the truth of the unique games conjecture. Certain stronger forms of the conjecture have been disproved.

A different form of the conjecture postulates that distinguishing the case when the value of a unique game is at least 1 − δ from the case when the value is at most ε is impossible for polynomial-time algorithms (but perhaps not NP-hard). This form of the conjecture would still be useful for applications in hardness of approximation.

The constant δ > 0 in the above formulations of the conjecture is necessary unless P = NP. If the uniqueness requirement is removed the corresponding statement is known to be true by the parallel repetition theorem, even when δ = 0.

Marek Karpinski and Warren Schudy[13] constructed linear time approximation schemes for dense instances of unique games problem.

In 2008, Prasad Raghavendra has shown that if the UGC is true, then for every constraint satisfaction problem (CSP) the best approximation ratio is given by a certain simple semidefinite programming (SDP) instance, which is in particular polynomial [1].

In 2010, Prasad Raghavendra and David Steurer defined the "Gap-Small-Set Expansion" problem, and conjectured that it is NP-hard. This conjecture implies the unique games conjecture.[14] It has also been used to prove strong hardness of approximation results for finding complete bipartite subgraphs.[15]

In 2010, Sanjeev Arora, Boaz Barak and David Steurer found a subexponential time approximation algorithm for the unique games problem.[16]

In 2012, it was shown that distinguishing instances with value at most 3/8 + δ from instances with value at least 1/2 is known to be NP-hard.[17]

In 2018, after a series of papers, a weaker version of the conjecture, called the 2-2 games conjecture, was proven. In a certain sense, this proves "a half" of the original conjecture [2],[3]. This also improves the best known gap for unique label cover: it is NP-hard to distinguish instances with value at most δ from instances with value at least 1/2.[18]

Notes[edit]

  1. ^ a b c Erica Klarreich (2011-10-06). "Approximately Hard: The Unique Games Conjecture". Simons Foundation. Retrieved 2012-10-29.
  2. ^ Dick Lipton (2010-05-05). "Unique Games: A Three Act Play". Gödel’s Lost Letter and P=NP. Retrieved 2012-10-29.
  3. ^ Khot, Subhash (2002), "On the power of unique 2-prover 1-round games", Proceedings of the thirty-fourth annual ACM symposium on Theory of computing, pp. 767–775, doi:10.1145/509907.510017, ISBN 1-58113-495-9, S2CID 207635974
  4. ^ The unique games conjecture is vacuously true if P = NP, as then every problem in NP would also be NP-hard.
  5. ^ Feige, Uriel; Goemans, Michel X. (1995), "Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT", Proc. 3rd Israel Symp. Theory of Computing and Systems, IEEE Computer Society Press, pp. 182–189
  6. ^ a b Håstad, Johan (1999), "Some Optimal Inapproximability Results", Journal of the ACM, 48 (4): 798–859, doi:10.1145/502090.502098, S2CID 5120748.
  7. ^ a b Khot, Subhash; Kindler, Guy; Mossel, Elchanan; O'Donnell, Ryan (2007), "Optimal inapproximability results for MAX-CUT and other two-variable CSPs?" (PDF), SIAM Journal on Computing, 37 (1): 319–357, doi:10.1137/S0097539705447372
  8. ^ Goemans, Michel X.; Williamson, David P. (1995), "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming", Journal of the ACM, 42 (6): 1115–1145, doi:10.1145/227683.227684, S2CID 15794408
  9. ^ Dinur, Irit; Safra, Samuel (2005), "On the hardness of approximating minimum vertex cover" (PDF), Annals of Mathematics, 162 (1): 439–485, doi:10.4007/annals.2005.162.439, retrieved 2010-03-05.
  10. ^ Khot, Subhash; Regev, Oded (2003), "Vertex cover might be hard to approximate to within 2 − ε", IEEE Conference on Computational Complexity: 379–
  11. ^ Chor, Benny; Sudan, Madhu (1998), "A geometric approach to betweenness", SIAM Journal on Discrete Mathematics, 11 (4): 511–523 (electronic), doi:10.1137/S0895480195296221, MR 1640920.
  12. ^ Charikar, Moses; Guruswami, Venkatesan; Manokaran, Rajsekar (2009), "Every permutation CSP of arity 3 is approximation resistant", 24th Annual IEEE Conference on Computational Complexity, pp. 62–73, doi:10.1109/CCC.2009.29, MR 2932455, S2CID 257225.
  13. ^ Karpinski, Marek; Schudy, Warren (2009), "Linear time approximation schemes for the Gale–Berlekamp game and related minimization problems", Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing: 313–322, arXiv:0811.3244, doi:10.1145/1536414.1536458, ISBN 9781605585062, S2CID 6117694
  14. ^ Raghavendra, Prasad; Steurer, David (2010), "Graph expansion and the unique games conjecture" (PDF), STOC'10—Proceedings of the 2010 ACM International Symposium on Theory of Computing, ACM, New York, pp. 755–764, doi:10.1145/1806689.1806792, MR 2743325, S2CID 1601199
  15. ^ Manurangsi, Pasin (2017), "Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis", in Chatzigiannakis, Ioannis; Indyk, Piotr; Kuhn, Fabian; Muscholl, Anca (eds.), 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), Leibniz International Proceedings in Informatics (LIPIcs), 80, Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 79:1–79:14, doi:10.4230/LIPIcs.ICALP.2017.79, ISBN 978-3-95977-041-5
  16. ^ Arora, Sanjeev; Barak, Boaz; Steurer, David (2015), "Subexponential algorithms for unique games and related problems", Journal of the ACM, 62 (5): Art. 42, 25, doi:10.1145/2775105, MR 3424199, S2CID 622344. Previously announced at FOCS 2010.
  17. ^ O'Donnell, Ryan; Wright, John (2012), "A new point of NP-hardness for unique games", Proceedings of the 2012 ACM Symposium on Theory of Computing (STOC'12), New York: ACM, pp. 289–306, doi:10.1145/2213977.2214005, MR 2961512, S2CID 6737664.
  18. ^ Subhash, K.; Minzer, D.; Safra, M. (October 2018). "Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion". 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS): 592–601. doi:10.1109/FOCS.2018.00062.

References[edit]

  • Khot, Subhash (2010), "On the Unique Games Conjecture", Proc. 25th IEEE Conference on Computational Complexity (PDF), pp. 99–121, doi:10.1109/CCC.2010.19.