Какие у нас есть доказательства (и против) предположения об уникальных играх?

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

Какие доказательства у нас есть для этого? Какие доказательства у нас есть против этого?

cc.complexity-theory unique-games-conjecture каве
источник

Не могли бы вы предоставить некоторые ссылки, ссылки и какие доказательства вы уже имеете за / против? В противном случае, сделайте этот вопрос типа «большой список» вики-сообществом.

Андрас Саламон

Я согласен, что это должно быть сообщество вики.

Мориц

как сформулировано, это определенно должно быть CW.

Суреш Венкат

Спасибо Даниэлю за ссылку на хороший опрос Хота. (Относительно старая статья в блоге «Вычислительная сложность»: blog.computationalcomplexity.org/2010/03/… )

Каве

Ответы:

Хот дал обзорную беседу UGC на CCC 2010. рецензия находится здесь . Последний сегмент (внизу страницы 30) имеет свое мнение по этому вопросу.

Даниэль Апон
источник

Другой интересный обзор о UGC, сделанный Хотом, цитируется в [1], который более ориентирован на математику:

Хот Хот, Непринимаемость NP-полных задач, Дискретный анализ Фурье и Геометрия , ICM 2010.

[1] С. Хот, О гипотезе уникальных игр , CCC 2010.

Кава
источник