как можно показать, какова связь между «гипотезой об уникальных играх» и «теоремой PCP»? Как объяснить, что «гипотеза об уникальных играх» является более сильной формой «теоремы PCP»?
как можно показать, какова связь между «гипотезой об уникальных играх» и «теоремой PCP»? Как объяснить, что «гипотеза об уникальных играх» является более сильной формой «теоремы PCP»?
Связанная гипотеза Хота подразумевает теорему PCP с совершенной полнотой: ожидается, что доказательство даст маркировку вершин. Верификатор выбирает случайное ребро, запрашивает его конечные точки и принимает, если ограничение выполняется.
Чтобы получить теорему PCP с полной полнотой из гипотезы об уникальных играх, вам нужно, как пишет Боаз, преобразовать PCP в одну с совершенной полнотой. Один из способов сделать это:
Добавьте новые переменные по одной на ограничение и измените ограничение, чтобы оно было выполнено, если новая переменная имеет значение true, или же если ограничение ранее было выполнено. Теперь вопрос сводится к нахождению лечащему врачу для принятия решения , если множество т бит (= новые вары) имеет сумму в большинстве или , по крайней мере ( 1 - х ) ⋅ м . Это кажется нетривиальным вопросом, но проще, чем теорема PCP.
Вы можете спросить, существует ли простое преобразование для преобразования PCP с несовершенной полнотой в одного с совершенной полнотой. Я думаю, что это, вероятно, можно сделать проще, чем доказать теорему PCP, но в настоящий момент я не осознаю очень простой аргумент.