Teorema de PCP: paso de reducción del alfabeto

Lo que sigue puede parecer estúpido (y eso probablemente refleja mi pobre comprensión, así que tengan paciencia conmigo)

Tenía una consulta sobre el teorema de PCP. Sabemos que después de los primeros tres pasos a saber. Reducción de grados, expansión y amplificación de huecos , tenemos un gráfico de restricción con huecos mejorados y un gran tamaño del alfabeto (como Σ d t ). Es este problema el que aborda el paso de reducción del alfabeto.$G$$\Sigma^{d^t}$

Mi pregunta es que como se indica en las notas de clase de Venkat Guruswami Introducción a la Composición , me parece que la idea de alto nivel es para expresar la restricción sobre un borde de correo como una restricción de Boole sobre las variables booleanas. Esto por sí solo no logra nada y también necesitamos aplicar la reducción de PCP, P e , en este borde. Esto "parece" una invocación recursiva de PCP y aquí es donde empiezo a preocuparme un poco. Parece que esta invocación recursiva volvería a volar el tamaño del alfabeto.$c_e$$e$$P_e$

Los autores han ofrecido alguna explicación al observar que esta recursión tiene un "caso base", es decir, la reducción de PCP "interna" se aplica solo a restricciones de tamaño constante.

(Por esto entiendo que la recursividad interior se invoca sólo cuando estamos ante limitaciones más de un solo filo que es una restricción binaria, pero todavía no han llegado aún más el temor de que de alguna manera todavía podríamos volar el tamaño del alfabeto en lugar de reducirlo). Para mí, todavía parece que una repetición recursiva del paso de amplificación de brecha solo empeorará las cosas al explotar el tamaño del alfabeto a menos que incorporemos medidas para manejar el caso base de manera un poco diferente.$c_e$

Espero que mi consulta (por tonta que sea) sea probablemente clara. Por favor, hágame saber qué parte esencial me estoy perdiendo (o he entendido mal).

Estás preguntando por la prueba de Dinur del teorema de PCP. El paso de reducción del alfabeto usa un PCP, pero el PCP tiene parámetros muy diferentes del que usted construye, y no necesariamente tiene que usar la recursividad para construirlo. En particular, en la prueba de Dinur, debido a que este PCP interno para la reducción del alfabeto se aplica en una entrada de tamaño constante, no nos importa si tiene una gran explosión (digamos exponencial o incluso más que eso), lo que hace que sea relativamente fácil dar un Construcción directa de un PCP suficientemente bueno.

La prueba completa, incluida esta etapa, se describe en varios lugares (consulte la respuesta a esta pregunta ), por lo que puede encontrar una descripción diferente que le guste más. En particular, en mi libro de texto de complejidad con Sanjeev Arora, esto está cubierto en los Capítulos 11 y 22, ofrecemos dos formas alternativas de lograr el paso de reducción del alfabeto. Uno está usando PCP basado en Hadamard en el texto principal. Pero quizás la variante autónoma más simple es la construcción elaborada en el ejercicio 22.5. También tenemos una tabla, en la Sección 22.2.1, que muestra exactamente lo que el paso de la prueba le hace al tamaño del alfabeto (y otros parámetros como el error de solidez, el tamaño y el número de consultas) y eso puede calmar su preocupación.