36
правок
Изменения
Нет описания правки
Доказательство:
# Из программы <tex>Verifier</tex> видно, что она работает за <tex>O(n \cdot |input|) = O(poly(|input|))</tex>.
# Если <tex>\varphi</tex> имеет ровно <tex>k</tex> удовлетворяющих наборов, то существует такая программа <tex>Prover</tex>, что <tex>P(VP(x)) = 1</tex>. Такая программа:
## Присылает, например, первое простое число, большее <tex>max(2^n, k_p)</tex>, и сертификат.
