Problème technique avec la preuve du théorème PCP

Je lis la preuve d' ici et je suis tombé sur un problème technique (pourtant crucial). Je sais que c'est assez spécifique et le contexte est problématique, mais je n'ai pas pu le comprendre moi-même.

Aux pages 51 et 55, après avoir présenté les vérificateurs "standard", ils se tournent pour modifier les vérificateurs afin de vérifier les affectations fractionnées.

Dans le premier cas (p. 51), ils vérifient que sont à près du code polynomial, puis ils utilisent l'algèbre (+ zéro-testeurs) pour construire une famille de polynômes (avec un Sum- Vérifiez la propriété liée à la formule d'entrée) que chacun peut être évalué à un point donné 3 valeurs de chacun de (les mots de code du placard de code polynomial à ).$f_1,\dots,f_k$$0.01$$\widetilde{f}_1,\dots,\widetilde{f}_k$$f_1,\dots,f_k$

Dans le second cas (p. 55), ils vérifient que sont proches d'être linéaires, puis ils définissent une fonction comme étant une somme spéciale de telle sorte que puisse être évalué à un point donné des valeurs de chacun de (le placard des fonctions linéaires à ).$f_1,\dots,f_k$$0.01$$f$$\widetilde{f}_1,\dots,\widetilde{f}_k$$f$$\widetilde{f}_1,\dots,\widetilde{f}_k$$f_1,\dots,f_k$

Ensuite, dans les deux cas, ils effectuent des tests (Sum-Check ou Tensor + Hadamard) sur les valeurs d'un polynôme aléatoire dans la famille / .$\widetilde{f}$

Mon problème est que la procédure de reconstruction des valeurs requises de chacun des peut fournir des valeurs incorrectes avec une probabilité constante non négligeable . De plus, la probabilité que toutes les valeurs soient reconstruites correctement est très faible, seulement pour une constante . Et cela est vrai pour les deux cas.$\widetilde{f}_i$$c^k$$c$

Cela peut être mauvais car certaines étapes des vérificateurs nécessitent d'obtenir des valeurs de la fonction cible / un polynôme de la famille whp$f$

Donc, nous devons amplifier la probabilité de réussite en utilisant à plusieurs reprises la «procédure algébrique de reconstruction» quelques fois pour chaque .$O(\log k)$$\widetilde{f}_i$

Maintenant, cela signifie que l'explosion de la complexité de la requête de la sous-routine (relativement à la complexité de la requête des vérificateurs d'origine) est légèrement plus grande que , c'est-à-dire qu'elle est (contrairement à la "garanti" - "souhaité" explosion dans l'énoncé des théorèmes).$k$$O(k\log k)$$O(k)$

Est-ce un problème ou manque-t-il quelque chose (que je suis probablement)?

La complexité de la requête utilisée dans cet article est et .$O(1)$$O(poly(logn))$

Pour le lemme 3.1, il est à noter que la complexité de la requête utilisée est .$O(1)$

Si la question est de savoir comment le lemme 3.1 se généralise à une complexité de requête non constante, cela pose un problème en dehors de .$O(poly(f(n)))$

Ce problème est contourné en composant un vérificateur qui réduit la complexité des requêtes à (lemme 4.4).$O(1)$