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