Technisches Problem mit dem PCP-Theorembeweis

Ich lese den Beweis von hier und bin auf ein technisches (aber entscheidendes) Problem gestoßen. Ich weiß, dass dies ziemlich spezifisch und der Kontext problematisch ist, aber ich konnte es selbst nicht herausfinden.

Auf den Seiten 51 und 55 ändern sie nach der Präsentation der "Standard" -Verifizierer die Verifizierer, um die geteilten Zuordnungen zu überprüfen.

Im ersten Fall (p. 51) kontrollieren , dass sie $f_1,\dots,f_k$ sind $0.01$ -Schließen an den Polynom - Code, und verwenden sie die Algebraisierung (+ Null-Tester) , eine Familie von Polynomen (mit einer Summe zu konstruieren -Überprüfen Sie die Eigenschaft in Bezug auf die Eingabeformel, dass jede an einem Punkt ausgewertet werden kann, wenn 3 Werte von $\widetilde{f}_1,\dots,\widetilde{f}_k$ (die Codewörter des Polynomcode-Schranks zu $f_1,\dots,f_k$ ) gegeben sind.

Im zweiten Fall (p. 55) , sie prüfen , dass $f_1,\dots,f_k$ sind $0.01$ -Schließen zu linear und dann definieren sie eine Funktion $f$ eine spezielle Summe sein $\widetilde{f}_1,\dots,\widetilde{f}_k$ solchen dass $f$ an einem Punkt ausgewertet werden kann, wenn Werte von $\widetilde{f}_1,\dots,\widetilde{f}_k$ (der lineare Funktionsschrank entspricht $f_1,\dots,f_k$ ).

Dann führen sie in beiden Fällen Tests (Sum-Check oder Tensor + Hadamard) an den Werten eines zufälligen Polynoms in der Familie / $\widetilde{f}$ .

Mein Problem ist, dass das Verfahren zur Rekonstruktion der erforderlichen Werte von jedem von $\widetilde{f}_i$ falsche Werte mit einer nicht zu vernachlässigenden konstanten Wahrscheinlichkeit liefern kann . Darüber hinaus ist die Wahrscheinlichkeit, dass alle Werte korrekt rekonstruiert werden, sehr gering, nur $c^k$ für eine Konstante $c$ . Dies gilt für beide Fälle.

Dies kann schlecht sein, da einige der Schritte der Verifizierer erforderlich sind, um Werte der Zielfunktion $f$ / a-Polynom von der Familie whp zu erhalten

$O(\log k)$$\widetilde{f}_i$

$k$$O(k\log k)$$O(k)$

Ist das ein Problem oder fehlt mir etwas (was ich wahrscheinlich bin)?

$O(1)$$O(poly(logn))$

$O(1)$

$O(poly(f(n)))$

$O(1)$