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)?

cc.complexity-theory pcp

— Don Fanucci
źródło

Przepraszam, jeśli to powinno być oczywiste, ale gdzie jest twierdzenie o twierdzeniach o wysadzeniu

? Na podstawie pobieżnego odczytu

wydaje się być dowolną stałą liczbą całkowitą (prawda?).

O (k)

$O(k)$

k

$k$

— Klemens C.,

@ClementC. Spójrz na definicje ponumerowane 3.2 i 3.3 w połączeniu z lematem rekurencyjnym kompozycji (a przede wszystkim na dowód). Zauważ, że jedynym miejscem, w którym używana jest normalna weryfikator formy do sprawdzania podzielonych przypisań, jest dowód lematu kompozycji (w rzeczywistości w każdym innym miejscu jest to „wielka odpowiedzialność”, z którą należy sobie radzić przy konstruowaniu weryfikatorów). Tam, w dowodzie,

jest nie stała w ogóle.

k

$k$

— Don Fanucci,

Dobra, jest używana dla

. Jednak do zastosowania w dowodzeniu twierdzenia PCP w następstwie 3.3 i twierdzeniu 3.5,

, więc (niezależnie od tego, czy ten dodatkowy

rzeczywiście powinien tu być, czy nie), to jest rzeczywiście stała.

p = Q (n)

$p=Q(n)$

Q (n) = 1

$Q(n)=1$

\log k

$\log k$

— Klemens C.

@ClementC. Dzięki, masz rację, że kiedy używamy kompozycji, używamy stałej

p

$p$

— Don Fanucci

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).

— Lem n
źródło