Теорема PCP - Шаг сокращения алфавита

То, что следует, может показаться глупым (и это, вероятно, отражает мое плохое понимание - поэтому, пожалуйста, потерпите меня)

У меня был вопрос по теореме PCP. Мы знаем, что после первых трех шагов, а именно. Уменьшение степени, расширение и усиление разрыва, у нас есть граф ограничений с улучшенным зазором и огромным размером алфавита (например, Σ d t ). Именно эту проблему решает шаг сокращения алфавита.$G$$\Sigma^{d^t}$

Мой вопрос заключается в том, что, как изложено в примечаниях к лекции Венката Гурусвами « Введение в композицию» , мне кажется, что идея высокого уровня состоит в том, чтобы выразить ограничение для ребра e как логическое ограничение для булевых переменных. Это само по себе ничего не дает, и мы также должны применить снижение ПЦФ, P e , к этому краю. Это «похоже» на рекурсивный вызов PCP, и здесь я начинаю немного волноваться. Кажется, что этот рекурсивный вызов снова увеличит размер алфавита.$c_e$$e$$P_e$

Авторы предложили некоторое объяснение, отметив, что эта рекурсия имеет «базовый случай», а именно - «внутреннее» сокращение PCP применяется только к ограничениям постоянного размера.

(Под этим я понимаю , что внутренняя рекурсии получает вызывается только тогда , когда мы смотрим на ограничения более одного ребра , который является двоичным ограничение, но до сих пор я еще не пришел через страх , что - то мы все еще могли бы взрывать размер алфавита вместо того, чтобы уменьшить его). Мне все еще кажется, что рекурсивное повторение шага Amplification Gap только ухудшит ситуацию, взорвав размер алфавита, если мы не включим меры для обработки базового случая немного по-другому.$c_e$

Я надеюсь, что мой запрос (как бы глупый он ни был), вероятно, ясен. Пожалуйста, дайте мне знать, какую важную часть я пропустил (или неправильно понял).

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

Все доказательства, включая этот этап, описаны в нескольких местах (см. Ответ на этот вопрос ), и поэтому вы можете найти другое описание, которое вам больше нравится. В частности, в моем учебнике по сложности с Sanjeev Arora, который описан в главах 11 и 22, мы предлагаем два альтернативных способа достижения стадии сокращения алфавита. Один из них использует основанного на Адамаре PCP в основном тексте. Но, возможно, самый простой автономный вариант - конструкция, разработанная в упражнении 22.5. У нас также есть таблица в Разделе 22.2.1, которая показывает, что именно шаг доказательства делает с размером алфавита (и другими параметрами, такими как ошибка правильности, размер и количество запросов), и который может развеять ваше беспокойство.