Problem techniczny z dowodem twierdzenia PCP

Czytam stąd dowód i natknąłem się na problem techniczny (ale kluczowy). Wiem, że jest to dość specyficzne i kontekst jest problematyczny, ale sam nie mogłem tego pojąć.

Na stronach 51 i 55, po przedstawieniu „standardowych” weryfikatorów, przechodzą do modyfikacji weryfikatorów w celu sprawdzenia podzielonych zadań.

W pierwszym przypadku (s. 51) sprawdzają, czy $f_1,\dots,f_k$ są $0.01$ zamykają się na kod wielomianowy, a następnie wykorzystują Algebraizację (+ testery zerowe) do konstruowania rodziny wielomianów (z sumą -Sprawdź właściwość związaną z formułą wejściową), że każdą można ocenić w punkcie podanym 3 wartościami każdego z $\widetilde{f}_1,\dots,\widetilde{f}_k$ (słowa kodowe wielomianowego kodu szafy do $f_1,\dots,f_k$ ).

W drugim przypadku (s. 55) sprawdzają, czy $f_1,\dots,f_k$ mają wartość są bliskie liniowości, a następnie definiują funkcję jako specjalną sumę takie, że może być oceniany w miejscu danej wartości każdego z (Pomiary liniowe szafy ).$0.01$$f$$\widetilde{f}_1,\dots,\widetilde{f}_k$$f$$\widetilde{f}_1,\dots,\widetilde{f}_k$$f_1,\dots,f_k$

Następnie w obu przypadkach przeprowadzają testy (Sum-Check lub Tensor + Hadamard) na wartościach losowego wielomianu w rodzinie / .$\widetilde{f}$

Mój problem polega na tym, że procedura rekonstrukcji wymaganych wartości każdego z może dostarczyć niepoprawne wartości z pewnym stałym prawdopodobieństwem . Ponadto prawdopodobieństwo, że wszystkie wartości zostaną poprawnie zrekonstruowane, jest bardzo niskie, tylko dla niektórych stałych . Dotyczy to obu przypadków.$\widetilde{f}_i$$c^k$$c$

Może to być złe, ponieważ niektóre etapy weryfikatorów wymagają uzyskania wartości funkcji docelowej / a wielomianu z rodziny whp$f$

Musimy więc zwiększyć prawdopodobieństwo sukcesu poprzez wielokrotne stosowanie „procedury algebraicznej rekonstrukcji” trochę razy dla każdego .$O(\log k)$$\widetilde{f}_i$

Oznacza to, że powiększenie złożoności zapytania podprogramu (w stosunku do złożoności zapytania oryginalnych weryfikatorów) jest nieco większe niż , tzn. Jest to (w przeciwieństwie do „gwarantowane” - „pożądane” wysadzenie w twierdzeniu twierdzeń).$k$$O(k\log k)$$O(k)$

Czy to problem, czy coś mi brakuje? (Prawdopodobnie jestem)?

Złożoność zapytania zastosowana w tym artykule to $O(1)$ i $O(poly(logn))$ .

W przypadku Lemma 3.1 zauważono, że złożoność zapytań to $O(1)$ .

Jeśli pytanie brzmi: w jaki sposób Lemma 3.1 uogólnia się na niestałą złożoność zapytań, stanowi to problem poza $O(poly(f(n)))$ .

Problem ten jest omijany przez skomponowanie weryfikatora, który zmniejsza złożoność zapytań do $O(1)$ (Lemma 4.4).