Théorème du PCP - Étape de réduction de l'alphabet

Ce qui suit peut sembler stupide (et cela reflète probablement ma mauvaise compréhension - alors soyez patient avec moi)

J'avais une requête sur le théorème du PCP. Nous savons qu'après les trois premières étapes, à savoir. Réduction de degré, expansion et amplification de l'écart, nous avons un graphe de contraintes avec un écart amélioré et une taille d'alphabet énorme (comme Σ d t ). C'est ce problème que l'étape de réduction de l'alphabet résout.$G$$\Sigma^{d^t}$

Ma question est que, comme indiqué dans les notes de cours de Venkat Guruswami Introduction à la composition , il me semble que l'idée de haut niveau est d'exprimer la contrainte sur une arête e comme une contrainte booléenne sur des variables booléennes. Cela en soi n'aboutit à rien et nous devons également appliquer la réduction PCP, P e , sur ce bord. Cela "ressemble" à une invocation récursive du PCP et c'est là que je commence à m'inquiéter un peu. Il semble que cette invocation récursive ferait exploser à nouveau la taille de l'alphabet.$c_e$$e$$P_e$

Les auteurs ont fourni quelques explications en observant que cette récursivité a un "cas de base" - à savoir - la réduction "intérieure" du PCP ne s'applique qu'aux contraintes de taille constante.

(Par cela, je comprends que la récursion intérieure n'est invoquée que lorsque nous examinons les contraintes sur un seul bord qui est une contrainte binaire, mais je ne suis pas encore tombé sur la crainte que nous puissions encore faire exploser la taille de l'alphabet au lieu de le rétrécir). Pour moi, il semble toujours qu'une répétition récursive de l'étape d'amplification de l'écart ne fera qu'aggraver les choses en faisant exploser la taille de l'alphabet, sauf si nous incorporons des mesures pour gérer le cas de base un peu différemment.$c_e$

J'espère que ma requête (aussi idiote soit-elle) est probablement claire. Veuillez me faire savoir quelle partie essentielle me manque (ou que j'ai mal comprise).

Vous posez des questions sur la preuve de Dinur du théorème du PCP. L'étape de réduction de l'alphabet utilise un PCP, mais le PCP a des paramètres très différents de celui que vous construisez, et vous n'avez pas nécessairement à utiliser la récursivité pour le construire. En particulier, dans la preuve de Dinur, parce que ce PCP interne pour la réduction de l'alphabet est appliqué sur une entrée de taille constante, peu nous importe qu'il ait une explosion énorme (disons exponentielle ou même plus que cela), ce qui rend relativement facile de donner un construction directe d'un PCP suffisamment bon.

La preuve complète, y compris cette étape, est décrite à plusieurs endroits (voir la réponse à cette question ), et vous pouvez donc trouver une description différente que vous préférez. En particulier, dans mon manuel de complexité avec Sanjeev Arora, cela est couvert dans les chapitres 11 et 22, nous vous proposons deux manières alternatives de réaliser l'étape de réduction de l'alphabet. L'un utilise le PCP basé sur Hadamard dans le texte principal. Mais peut-être que la variante autonome la plus simple est la construction élaborée dans l'exercice 22.5. Nous avons également un tableau, à la section 22.2.1, qui montre exactement quelle étape de la preuve fait la taille de l'alphabet (et d'autres paramètres tels que l'erreur de solidité, la taille et le nombre de requêtes) et qui peut apaiser votre inquiétude.