Вопросы с тегом «unique-games-conjecture»

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

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

22
Что такое UG-твердость и чем она отличается от NP-жесткости, основанной на гипотезе уникальных игр?

Есть много результатов неприемлемости, которые основаны на гипотезе об уникальных играх. Например, Предполагая гипотезу об уникальных играх, трудно вычислить аппроксимацию задачи максимального разреза в пределах коэффициента R для любой константы R > R GW . (Здесь R GW = 0,878… - коэффициент...

19
Визуализация уникальных игр

Как бы вы нарисовали картинку, чтобы проиллюстрировать уникальную игру? Это для презентации «Текущие события» по уникальным играм на следующем совместном собрании AMS и для выпуска буклета. Пример вида иллюстраций, выполненных в прошлом, находится на...

17
Есть ли простой аргумент, который показывает, что гипотеза об уникальных играх подразумевает теорему PCP

как можно показать, какова связь между «гипотезой об уникальных играх» и «теоремой PCP»? Как объяснить, что «гипотеза об уникальных играх» является более сильной формой «теоремы...

16
UGC твердость предиката

Фон : В оригинальной статье UGC Субхаша Хота ( PDF ) он доказывает, что UG-сложность определения того, допускает ли заданный экземпляр CSP ограничения всех форм Не-все-равные (a, b, c) по троичному алфавиту 1 - ограничений или не существует никаких заданий, удовлетворяющих 8ϵϵ\epsilonиз...

9
Чисто теоретико-графическое объяснение редукции от уникального покрытия этикетки до Max-Cut

Я изучаю гипотезу об уникальных играх и известное сведение к Max-Cut из Khot et al. Из их статьи и из других источников в Интернете большинство авторов используют (что для меня является) неявную эквивалентность между сокращением MAX-CUT и созданием конкретных тестов для длинных кодов. Из-за моей...