Jakie mamy dowody na (i przeciw) hipotezę o unikalnych grach?

Subhash KHOT „s Unikalne Gry Conjecture jest jednym z aktywnych obszarów badawczych w teorii złożoności.

Jakie mamy na to dowody? Jakie mamy na to dowody?

cc.complexity-theory unique-games-conjecture Kaveh
źródło

Czy możesz podać jakieś referencje, linki i jakie dowody masz już za / przeciw? W przeciwnym razie zadaj pytanie typu Biglist jako wiki społeczności.

András Salamon,

Zgadzam się, że powinna to być wiki społeczności.

Moritz

jak powiedziano, zdecydowanie powinien to być CW.

Suresh Venkat

Dzięki Daniel za link do miłej ankiety Khota. (Stosunkowo starszy powiązany post na blogu Computational Complexity: blog.computationalcomplexity.org/2010/03/… )

Kaveh

Odpowiedzi:

Khot wygłosił mowę ankietową UGC na CCC 2010. Zapis jest tutaj . Ostatni segment (na dole strony 30) ma swoje opinie na ten temat.

Daniel Apon
źródło

Kolejna interesująca ankieta na temat UGC autorstwa Khota cytowana w [1], która jest bardziej zorientowana matematycznie:

S. Khot, Niedopuszczalność problemów NP-zupełnych, dyskretna analiza Fouriera i geometria , ICM 2010.

[1] S. Khot, On the Unique Games Conjecture , CCC 2010.

Kaveh
źródło