Техническая проблема с доказательством теоремы PCP

12

Отсюда я читаю доказательства и наткнулся на техническую (хотя и крайне важную) проблему. Я знаю, что это довольно специфично, и контекст проблематичен, но я не мог понять это сам.

На страницах 51 и 55 после представления «стандартных» верификаторов они поворачиваются, чтобы модифицировать верификаторы для проверки разделенных назначений.

В первом случае (стр. 51) они проверяют, что f1,,fk являются 0.01 близкими к полиномиальному коду, а затем они используют алгебраизацию (+ тестеры нулей) для построения семейства полиномов (с суммой -Check свойство , относящееся к входной формуле) , что каждый из них может быть оценен в точке , заданной 3 значение каждого из f~1,,f~k (кодовые слова полинома кода к шкафу f1,,fk ).

Во втором случае (стр. 55) они проверяют , что f1,,fk в 0.01 -близких к линейной, а затем они определяют функцию f , чтобы быть специальной суммой f~1,,f~k таким что f может быть оценена в точке , заданной величины каждого из f~1,,f~k (линейные функции шкафу f1,,fk ).

Тогда в обоих случаях они выполняют тесты (Sum-Check или Tensor + Адамара) на значения случайного полинома в семье / f~ .

Моя проблема заключается в том , что процедура восстановления требуемых значений каждого из f~i могу предоставить неправильные значения с некоторым пренебрежимо малой вероятностью постоянной . Более того, вероятность того, что все значения восстановлены правильно, очень мала, только ck для некоторой константы c . И это верно для обоих случаев.

Это может быть плохо, так как некоторые из этапов верификаторов требуют получения значений целевой функции f / многочлена из семейства whp

O(logk)f~i

kO(klogk)O(k)

Это проблема, или я что-то упустил (что я, вероятно, я)?

Дон фануччи
источник
O(k)k
k
p=Q(n)Q(n)=1logk
p

Ответы:

1

O(1)O(poly(logn))

O(1)

O(poly(f(n)))

O(1)

Лем н
источник