Лемма о соотношении coNP и IP — различия между версиями
м |
м |
||
Строка 1: | Строка 1: | ||
+ | {{В разработке}} | ||
+ | |||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
Строка 70: | Строка 72: | ||
:'''Шаг m''' | :'''Шаг m''' | ||
: <tex>P(A_{m-1}(r_m) \ne \tilde{A}_{m-1}(r_m)) \ge 1 - \frac d p</tex>. Значит с такой вероятностью ''Verifier'' получит <tex>\tilde{A}_m</tex> вместо <tex>A_m</tex>. Но так как на шаге <tex>m</tex> ''Verifier'' вычисляет <tex>A_m</tex> и сравнивает его с полученным от ''Prover'' 'а, то в этом случае ''Verifier'' вернет ''false''. | : <tex>P(A_{m-1}(r_m) \ne \tilde{A}_{m-1}(r_m)) \ge 1 - \frac d p</tex>. Значит с такой вероятностью ''Verifier'' получит <tex>\tilde{A}_m</tex> вместо <tex>A_m</tex>. Но так как на шаге <tex>m</tex> ''Verifier'' вычисляет <tex>A_m</tex> и сравнивает его с полученным от ''Prover'' 'а, то в этом случае ''Verifier'' вернет ''false''. | ||
+ | : | ||
+ | :Заметим, что если на каком-то шаге <tex>P(A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i))</tex>, то начиная со следующего шага ''Prover'' может посылать истинные значения <tex>A_i</tex> и в итоге ''Verifier'' вернёт '''true'''. | ||
+ | :Из описанного процесса видно, что с вероятностью большей либо равной <tex>(1 - \frac d p) ^ m</tex> мы дойдем до последнего шага и будем имееть <tex>\tilde{A}_n</tex> вместо <tex>A_n</tex>. Так как на шаге <tex>m</tex> ''Verifier'' вычисляет <tex>A_n</tex> и проверяет значение, то ''Verifier'' вернет ''false''. | ||
+ | :Оценим вероятность возврата ''Verifier'' 'ом ответа '''false'''. | ||
+ | :<tex>(1 - \frac d p) ^ m \ge (1 - \frac d {3dm})^m = (1 - \frac 1 {3m})^m = 1 - \frac 1 3 + \frac{m(m - 1)}{2 (3m)^2} - \frac{m(m-1)(m-2)}{6 (3m)^3} + \ldots \ge \frac 2 3</tex>. | ||
− | + | Таким образом, построенный нами ''Verifier'' корректен, а значит лемма доказана. | |
}} | }} | ||
Версия 20:57, 1 июня 2012
Определение: |
имеет ровно удовлетворяющих наборов . |
Лемма (1): |
. |
Доказательство: |
Следует из леммы (1). |
Лемма (2): |
. |
Доказательство: |
Для доказательства леммы построим программы Verifier и Prover из определения класса . Сперва арифметизуем формулу . Пусть полученный полином имеет степень .По лемме (1) вместо условия , можно проверять условие .Приступим к описанию Verifier'а. Шаг 0 Запросим у Prover'а такое простое число знаем, , следовательно на эти операции у Verifier'а уйдёт полиномиальное от размера входа время. , что . Проверим на простоту и на принадлежность заданному промежутку. Как мыДалее будем проводить все вычисления модулю .Попросим Prover 'а прислать Verifier 'у формулу . Заметим, что размер формулы будет полином от длины входа Verifier 'а, так как полином от одной переменной степени не выше, чем , а значит его можно представить в виде .Проверим следующее утверждение: (здесь и далее под словом «проверим» будем подразумевать следующее: если утверждение верно, Verifier продолжает свою работу, иначе он прекращает свою работу и возвращет false).Шаг i Пусть . Отправим программе Prover.Попросим Prover 'а прислать Verifier 'у формулу .Проверим следующее утверждение: .Шаг m Пусть . Отправим программе Prover.Попросим программу Prover прислать Verifier 'у значение .Проверим следующее утверждение: . А также сами подставим в и проверим правильность присланного значения .Возвращаем true. Докажем теперь, что построенный таким образом Verifier — корректный. Таким образом, нужно доказать:
|
Лемма (3): |
. |
Доказательство: |
Сведём язык к языку следующим образом: , где — количество различных переменных в формуле .Очевидно, что По лемме (2) . . Тогда . Так как , то . |