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

17

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

JS
источник

Ответы:

19

Связанная гипотеза Хота подразумевает теорему PCP с совершенной полнотой: ожидается, что доказательство даст маркировку вершин. Верификатор выбирает случайное ребро, запрашивает его конечные точки и принимает, если ограничение выполняется.2-1

Чтобы получить теорему PCP с полной полнотой из гипотезы об уникальных играх, вам нужно, как пишет Боаз, преобразовать PCP в одну с совершенной полнотой. Один из способов сделать это:(с,s)

Добавьте новые переменные по одной на ограничение и измените ограничение, чтобы оно было выполнено, если новая переменная имеет значение true, или же если ограничение ранее было выполнено. Теперь вопрос сводится к нахождению лечащему врачу для принятия решения , если множество т бит (= новые вары) имеет сумму в большинстве или , по крайней мере ( 1 - х ) м . Это кажется нетривиальным вопросом, но проще, чем теорема PCP.(1-с)м(1-s)м

Ирит Динур
источник
22

s<1с>s

с1s0

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

Боаз Барак
источник