Изменения

Перейти к: навигация, поиск

Sharp SAT

1 байт добавлено, 23:04, 22 апреля 2010
Нет описания правки
Проверим следующее утверждение: <tex>A_0(0) + A_0(1) = k</tex>.
Заметим, что размер формулы <tex>A_0(x_1)</tex> будет полином от длинны входа <tex>Verifier</tex>'а. Этот факт следует из того, что формула имеет степень меньшую либо равную <tex>d</tex> , и она от одной переменной. Поэтому её можно представить так: <tex>A_0(x) = \sum_{i = 0}^{d} C_i \cdot x ^ i</tex>, и попросить <tex>Prover</tex>'а прислать только сами коэффициенты <tex>C_i</tex> по модулю <tex>p</tex>.
Шаг 1.
36
правок

Навигация