Teorema do PCP - Etapa de redução do alfabeto

O que se segue pode parecer estúpido (e isso provavelmente reflete meu fraco entendimento - por isso, tenha paciência comigo)

Eu tive uma consulta no teorema do PCP. Sabemos que após os três primeiros passos viz. Redução de Grau, Expansão e Amplificação de Gap, temos um gráfico de restrição com gap aprimorado e tamanho enorme de alfabeto (como Σ d t ). É esse problema abordado pela etapa de redução do alfabeto.$G$$\Sigma^{d^t}$

Minha pergunta é que, conforme descrito nas notas de aula de Venkat Guruswami, Introdução à composição , parece-me que a idéia de alto nível é expressar a restrição sobre uma borda e como uma restrição booleana sobre variáveis ​​booleanas. Isso, por si só, não alcança nada e também precisamos aplicar a redução de PCP, P e , nessa borda. Isso "parece" uma invocação recursiva do PCP e é aqui que começo a ficar um pouco preocupado. Parece que essa invocação recursiva explodiria o tamanho do alfabeto novamente.$c_e$$e$$P_e$

Os autores ofereceram alguma explicação observando que essa recursão tem um "caso base" - a saber, a redução "interna" de PCP se aplica apenas a restrições de tamanho constante.

(Por isso eu entendo que a recursividade interior é invocado apenas quando estamos a olhar para as restrições mais de uma única aresta que é uma restrição binário, mas ainda assim eu ainda não vir o medo que de alguma forma nós ainda pode explodir o tamanho do alfabeto em vez de encolher). Para mim, ainda parece que uma repetição recursiva da etapa Gap Amplification só piorará a situação ao aumentar o tamanho do alfabeto, a menos que incorporemos medidas para lidar com o caso base de maneira um pouco diferente.$c_e$

Espero que minha consulta (por mais boba que seja) seja provavelmente clara. Por favor, deixe-me saber que parte essencial estou perdendo (ou entendi mal).

Você está perguntando sobre a prova de Dinur do teorema do PCP. A etapa de redução do alfabeto usa um PCP, mas o PCP possui parâmetros muito diferentes daquele que você constrói e você não precisa necessariamente usar a recursão para construí-lo. Em particular, na prova de Dinur, porque esse PCP interno para a redução do alfabeto é aplicado em dados de tamanho constante, não nos importamos se ele tem uma explosão enorme (digamos exponencial ou até mais do que isso), o que facilita comparativamente construção direta de um PCP bom o suficiente.

A prova completa, incluindo esta etapa, é descrita em vários lugares (consulte a resposta a esta pergunta ) e, portanto, você pode encontrar uma descrição diferente que mais lhe agrade. Em particular, em meu livro de complexidade com Sanjeev Arora, abordado nos capítulos 11 e 22, oferecemos duas maneiras alternativas de alcançar a etapa de redução do alfabeto. Um está usando o PCP baseado em Hadamard no texto principal. Mas talvez a variante independente mais simples seja a construção elaborada no Exercício 22.5. Também temos uma tabela, na Seção 22.2.1, que mostra exatamente o que a etapa da prova faz com o tamanho do alfabeto (e outros parâmetros como erro de sonoridade, tamanho e número de consultas) e que podem atenuar sua preocupação.