Лемма о соотношении coNP и IP - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:05:38Z

rollbackEdits.php mass rollback

141.98.9.47 в 06:32, 1 сентября 2022

2022-09-01T06:32:45Z

Байдаров Андрей в 13:55, 4 июня 2012

2012-06-04T13:55:42Z

Байдаров Андрей в 13:46, 4 июня 2012

2012-06-04T13:46:36Z

Kirelagin в 13:40, 4 июня 2012

2012-06-04T13:40:03Z

Байдаров Андрей в 13:25, 4 июня 2012

2012-06-04T13:25:50Z

Байдаров Андрей в 13:23, 4 июня 2012

2012-06-04T13:23:47Z

Байдаров Андрей в 13:23, 4 июня 2012

2012-06-04T13:23:05Z

Kirelagin в 13:16, 4 июня 2012

2012-06-04T13:16:58Z

Байдаров Андрей в 13:09, 4 июня 2012

2012-06-04T13:09:37Z

← Предыдущая		Версия 16:05, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	{{В разработке}}		{{В разработке}}

← Предыдущая		Версия 06:32, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	{{В разработке}}		{{В разработке}}

@@ Строка 80: / Строка 80: @@
 :Вычислим вероятность того, что хотя бы раз корень был угадан.
 :<tex>P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) = 1 - (1 - \frac d p)^m \le 1 - (1 - \frac d {3dm})^m \le \frac 1 3</tex>.
-В последнем переходе мы воспользовались [http://ru.wikipedia.org/wiki/Ряд_Тейлора формулой Тейлора] для логарифма и экспоненты, а также тем, что <tex>m>0</tex>.
+:В последнем переходе мы воспользовались [http://ru.wikipedia.org/wiki/Ряд_Тейлора формулой Тейлора] для логарифма и экспоненты, а также тем, что <tex>m>0</tex>.
 Таким образом, построенный нами ''Verifier'' корректен, а значит лемма доказана.

@@ Строка 80: / Строка 80: @@
 :Вычислим вероятность того, что хотя бы раз корень был угадан.
 :<tex>P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) = 1 - (1 - \frac d p)^m \le 1 - (1 - \frac d {3dm})^m \le \frac 1 3</tex>.
 Таким образом, построенный нами ''Verifier'' корректен, а значит лемма доказана.

@@ Строка 60: / Строка 60: @@
 Докажем теперь, что построенный таким образом ''Verifier'' — корректный. Для этого нужно доказать следующие утверждения:
 # Построенный ''Verifier'' - вероятностная машина Тьюринга, совершающая не более полинома от длины входа действий.
-# <tex>\langle \varphi, k \rangle \in \#SAT \Rightarrow \exists \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \ge 2/3</tex>.
+# <tex>\langle \varphi, k \rangle \in \mathrm{\#SAT} \Rightarrow \exists \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \ge 2/3</tex>.
-# <tex>\langle \varphi, k \rangle \notin \#SAT \Rightarrow \forall \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \le 1/3</tex>.
+# <tex>\langle \varphi, k \rangle \notin \mathrm{\#SAT} \Rightarrow \forall \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \le 1/3</tex>.
 Докажем эти утверждения.
@@ Строка 72: / Строка 72: @@
 :<tex>\ldots</tex>
 :'''Шаг i'''
-:Заметим, что если на каком-то шаге <tex>A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)</tex>, то начиная со следующего шага ''Prover'' может посылать истинные значения <tex>A_j</tex> и в итоге ''Verifier'' вернёт '''true'''.
+:Заметим, что если на каком-то шаге <tex>A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)</tex>, то начиная со следующего шага ''Prover'' может посылать правильные <tex>A_j</tex> и в итоге ''Verifier'' вернёт '''true'''.
 :Для некоторого случайно выбранного <tex>r_i</tex> вероятность того, что <tex>A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)</tex>, то есть <tex>r_i</tex> — корень полинома <tex>(A_{i-1} - \tilde{A}_{i-1})(r_i)</tex>, имеющего степень не больше <tex>d</tex>, не превосходит <tex>\frac{d}{p}</tex>.
 :<tex>\ldots</tex>
 :'''Шаг m'''
-:Так как на последнем шаге ''Verifier'' сверяет истинное значение с полученным от ''Prover'', слово будет допущено только в том случае, когда ''Prover'' смог прислать верное значение, что в свою очередь возможно лишь если на одном из предыдущих шагов был верно угадан корень полинома.
+:Так как на последнем шаге ''Verifier'' полученным от ''Prover'' значение с непосредственно вычисленным, слово будет допущено только в том случае, когда ''Prover'' смог прислать верное значение, что в свою очередь возможно лишь если на одном из предыдущих шагов был верно угадан корень полинома.
+:
-:Посчитаем вероятность того, что ''Verifier'' хотя бы раз угадал корень.
+:Вычислим вероятность того, что хотя бы раз корень был угадан.
 :<tex>P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) = 1 - (1 - \frac d p)^m \le 1 - (1 - \frac d {3dm})^m \le \frac 1 3</tex>.

@@ Строка 78: / Строка 78: @@
 :Так как на последнем шаге ''Verifier'' сверяет истинное значение с полученным от ''Prover'', слово будет допущено только в том случае, когда ''Prover'' смог прислать верное значение, что в свою очередь возможно лишь если на одном из предыдущих шагов был верно угадан корень полинома.
+:
-:<tex>P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \le \frac d p \sum \limits_{i=0}^{m-1} (1 - \frac d p)^i = 1 - (1 - \frac d p)^m \le 1 - (1 - \frac d {3dm})^m = 1 - (1 - \frac 1 {3m})^m \le \frac 1 3</tex>.
+:<tex>P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) = 1 - (1 - \frac d p)^m \le 1 - (1 - \frac d {3dm})^m = 1 - (1 - \frac 1 {3m})^m \le \frac 1 3</tex>.
 Таким образом, построенный нами ''Verifier'' корректен, а значит лемма доказана.

@@ Строка 41: / Строка 41: @@
 '''Шаг i'''
-Пусть <tex>r_i = random(p)</tex>. Отправим <tex>r_i</tex> программе ''Prover''.
+Пусть <tex>r_i = random(0..p-1)</tex>. Отправим <tex>r_i</tex> программе ''Prover''.
 Попросим ''Prover'' 'а прислать ''Verifier'' 'у формулу <tex>A_i(x_{i+1}) = \sum\limits_{x_{i+2} = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A(r_1,\ldots, r_i, x_{i+1}, ..., x_m)</tex>.
@@ Строка 49: / Строка 49: @@
 '''Шаг m'''
-Пусть <tex>r_m = random(p)</tex>. Отправим <tex>r_m</tex> программе ''Prover''.
+Пусть <tex>r_m = random(0..p-1)</tex>. Отправим <tex>r_m</tex> программе ''Prover''.
 Попросим программу ''Prover'' прислать ''Verifier'' 'у значение <tex>A_m()= A(r_1, r_2, ..., r_m)</tex>.