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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:39:40Z

rollbackEdits.php mass rollback

217.79.179.7 в 03:35, 1 сентября 2022

2022-09-01T03:35:15Z

NikitaMarkovnikov в 17:30, 22 мая 2016

2016-05-22T17:30:37Z

NikitaMarkovnikov в 18:38, 12 мая 2016

2016-05-12T18:38:38Z

NikitaMarkovnikov в 17:53, 12 мая 2016

2016-05-12T17:53:35Z

NikitaMarkovnikov в 16:24, 10 мая 2016

2016-05-10T16:24:53Z

NikitaMarkovnikov в 18:40, 2 мая 2016

2016-05-02T18:40:36Z

NikitaMarkovnikov в 18:39, 2 мая 2016

2016-05-02T18:39:07Z

NikitaMarkovnikov в 18:37, 2 мая 2016

2016-05-02T18:37:01Z

NikitaMarkovnikov в 18:15, 2 мая 2016

2016-05-02T18:15:10Z

← Предыдущая		Версия 16:39, 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 Майкл Наки].
−	\|}
−
	== Подготовка к доказательству ==		== Подготовка к доказательству ==

← Предыдущая		Версия 03:35, 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 Майкл Наки].
		+	\|}
		+
	== Подготовка к доказательству ==		== Подготовка к доказательству ==

@@ Строка 52: / Строка 52: @@
 Докажем теперь, что построенный таким образом интерактивны протокол {{---}} корректный. Для этого нужно доказать следующие утверждения:
 # Построенный <tex>V</tex> {{---}} [[Вероятностные_вычисления._Вероятностная_машина_Тьюринга|вероятностная машина Тьюринга]], совершающая не более полинома от длины входа действий.
-# <tex>\langle \varphi, k \rangle \in \mathrm{\#SAT} \Rightarrow \exists P : \mathbb{P}(V_{P}(\langle \varphi, k \rangle)=1) \geqslant 2/{3}</tex> (Completeness).
+# <tex>\langle \varphi, k \rangle \in \mathrm{\#SAT} \Rightarrow \exists P : \mathbb{P}(V_{P}(\langle \varphi, k \rangle)=1) \geqslant 2/{3}</tex> ([[Интерактивные_протоколы._Класс_IP._Класс_AM|Completeness]]).
-# <tex>\langle \varphi, k \rangle \notin \mathrm{\#SAT} \Rightarrow \forall P :\mathbb{P}(V_{P}(\langle \varphi, k \rangle)=1) \leqslant 1/{3}</tex> (Soundness).
+# <tex>\langle \varphi, k \rangle \notin \mathrm{\#SAT} \Rightarrow \forall P :\mathbb{P}(V_{P}(\langle \varphi, k \rangle)=1) \leqslant 1/{3}</tex> ([[Интерактивные_протоколы._Класс_IP._Класс_AM|Soundness]]).
 Докажем эти утверждения.

@@ Строка 30: / Строка 30: @@
 :Если <tex>d=0</tex> или <tex>m=0</tex>, то <tex>V</tex> может проверить указанное выше условие сам и вернуть соответствующий результат. Иначе запросим у <tex>P</tex> такое простое число <tex>p</tex>, что <tex>3dm \leqslant p \leqslant 6dm</tex> (такое <tex>p</tex> существует в силу постулата Бертрана<ref>[http://ru.wikipedia.org/wiki/Постулат_Бертрана Wikipedia {{---}} Постулат Бертрана]</ref>. Проверим <tex>p</tex> на простоту и на принадлежность заданному промежутку. Как мы [[Класс P#Примеры задач и языков из P|знаем]], <tex>\mathrm{Primes} \in \mathrm{P}</tex>, следовательно на эти операции у <tex>V</tex> уйдёт полиномиальное от размера входа время.
-:Далее будем проводить все вычисления по модулю <tex>p</tex>, то есть над конечным полем <tex> \mathbb{F}_{p} </tex>, что не позволяет числам становиться слишком большими и упрощает анализ.
+:Далее будем проводить все вычисления по модулю <tex>p</tex>, то есть над конечным [[Определение поля и подполя, изоморфизмы полей | полем ]] <tex> \mathbb{F}_{p} </tex>, что не позволяет числам становиться слишком большими и упрощает анализ.
 :Попросим <tex>P</tex> прислать <tex>V</tex> формулу <tex>A_0(x_1)= \sum\limits_{x_2 = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A_\varphi(x_1, x_2, \ldots, x_m)</tex>. Заметим, что размер формулы <tex>A_0(x_1)</tex> будет полином от длины входа <tex>V</tex>, так как <tex>A_0(x_1)</tex> — полином степени не выше, чем <tex>d</tex>, от одной переменной, а значит его можно представить в виде <tex>A_0(x) = \sum\limits_{i = 0}^{d} C_i \cdot x ^ i</tex>.

@@ Строка 1: / Строка 1: @@
 {{Определение
 |definition=
@@ Строка 26: / Строка 28: @@
 ; '''Шаг 0'''
-:Если <tex>d=0</tex> или <tex>m=0</tex>, то <tex>V</tex> может проверить указанное выше условие сам и вернуть соответствующий результат. Иначе запросим у <tex>P</tex> такое простое число <tex>p</tex>, что <tex>3dm \leqslant p \leqslant 6dm</tex> (такое <tex>p</tex> существует в силу [http://ru.wikipedia.org/wiki/Постулат_Бертрана постулата Бертрана]). Проверим <tex>p</tex> на простоту и на принадлежность заданному промежутку. Как мы [[Класс P#Примеры задач и языков из P|знаем]], <tex>\mathrm{Primes} \in \mathrm{P}</tex>, следовательно на эти операции у <tex>V</tex> уйдёт полиномиальное от размера входа время.
+:Если <tex>d=0</tex> или <tex>m=0</tex>, то <tex>V</tex> может проверить указанное выше условие сам и вернуть соответствующий результат. Иначе запросим у <tex>P</tex> такое простое число <tex>p</tex>, что <tex>3dm \leqslant p \leqslant 6dm</tex> (такое <tex>p</tex> существует в силу постулата Бертрана<ref>[http://ru.wikipedia.org/wiki/Постулат_Бертрана Wikipedia {{---}} Постулат Бертрана]</ref>. Проверим <tex>p</tex> на простоту и на принадлежность заданному промежутку. Как мы [[Класс P#Примеры задач и языков из P|знаем]], <tex>\mathrm{Primes} \in \mathrm{P}</tex>, следовательно на эти операции у <tex>V</tex> уйдёт полиномиальное от размера входа время.
 :Далее будем проводить все вычисления по модулю <tex>p</tex>, то есть над конечным полем <tex> \mathbb{F}_{p} </tex>, что не позволяет числам становиться слишком большими и упрощает анализ.
@@ Строка 48: / Строка 50: @@
 :Возвращаем '''true'''.
-Докажем теперь, что построенный таким образом интерактивны протокол — корректный. Для этого нужно доказать следующие утверждения:
+Докажем теперь, что построенный таким образом интерактивны протокол {{---}} корректный. Для этого нужно доказать следующие утверждения:
-# Построенный <tex>V</tex> - [[Вероятностные_вычисления._Вероятностная_машина_Тьюринга|вероятностная машина Тьюринга]], совершающая не более полинома от длины входа действий.
+# Построенный <tex>V</tex> {{---}} [[Вероятностные_вычисления._Вероятностная_машина_Тьюринга|вероятностная машина Тьюринга]], совершающая не более полинома от длины входа действий.
 # <tex>\langle \varphi, k \rangle \in \mathrm{\#SAT} \Rightarrow \exists P : \mathbb{P}(V_{P}(\langle \varphi, k \rangle)=1) \geqslant 2/{3}</tex> (Completeness).
 # <tex>\langle \varphi, k \rangle \notin \mathrm{\#SAT} \Rightarrow \forall P :\mathbb{P}(V_{P}(\langle \varphi, k \rangle)=1) \leqslant 1/{3}</tex> (Soundness).
@@ Строка 58: / Строка 60: @@
 #По [[Арифметизация булевых формул с кванторами | лемме (2)]], если <tex>\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1  A_\varphi(x_1, \ldots, x_m)=k</tex>, то условия (*) выполняются, а значит, по построению протокола, существует такой <tex>P</tex>, что <tex>\mathbb{P}(V_{P}(\langle\varphi,k\rangle) = 1) = 1</tex>, для любой пары <tex>\langle\varphi,k\rangle \in \mathrm{\#SAT}</tex>.
 #Пусть количество наборов, удовлетворяющих <tex>\varphi</tex>, не равно <tex>k</tex>. Для того, чтобы <tex>V</tex> вернул '''true''', <tex>P</tex> должен посылать такие <tex>A_i</tex>, чтобы выполнялись все проверяемые условия. Посмотрим на то, что он может послать:
-:'''Шаг 0'''
+::;'''Шаг 0'''
-:Так как количество наборов, удовлетворяющих <tex>\varphi</tex>, не равно <tex>k</tex>, то <tex>P</tex> не может послать правильное <tex>A_0</tex>, поскольку в этом случае не выполнится условие <tex>A_0(0) + A_0(1) = k</tex>. Поэтому он посылает не <tex>A_0</tex>, а некое <tex>\tilde{A}_0</tex>.
+:::Так как количество наборов, удовлетворяющих <tex>\varphi</tex>, не равно <tex>k</tex>, то <tex>P</tex> не может послать правильное <tex>A_0</tex>, поскольку в этом случае не выполнится условие <tex>A_0(0) + A_0(1) = k</tex>. Поэтому он посылает не <tex>A_0</tex>, а некое <tex>\tilde{A}_0</tex>.
-:<tex>\ldots</tex>
+::;'''Шаг i'''
-:'''Шаг i'''
+:::Заметим, что если на каком-то шаге <tex>A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)</tex>, то начиная со следующего шага <tex>P</tex> может посылать правильные <tex>A_j</tex> и в итоге <tex>V</tex> вернёт '''true'''.
-:Заметим, что если на каком-то шаге <tex>A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)</tex>, то начиная со следующего шага <tex>P</tex> может посылать правильные <tex>A_j</tex> и в итоге <tex>V</tex> вернёт '''true'''.
+:::Для некоторого случайно выбранного <tex>r_i</tex> вероятность того, что <tex>A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)</tex>, не превосходит <tex>\dfrac{d}{p}</tex>, так как <tex>r_i</tex> — корень полинома <tex>(A_{i-1} - \tilde{A}_{i-1})(r_i)</tex>, имеющего степень не больше <tex>d</tex>, а, по основной теореме алгебры<ref>[https://ru.wikipedia.org/wiki/%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%B0%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D1%8B Wikipedia {{---}} Основная теорема алгебры]</ref>, полином имеет ровно <tex> d </tex> корней, и <tex> r_i \in \lbrace 0, \ldots, p -1 \rbrace</tex>.
-:Для некоторого случайно выбранного <tex>r_i</tex> вероятность того, что <tex>A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)</tex>, не превосходит <tex>\dfrac{d}{p}</tex>, так как <tex>r_i</tex> — корень полинома <tex>(A_{i-1} - \tilde{A}_{i-1})(r_i)</tex>, имеющего степень не больше <tex>d</tex>, а, по [https://ru.wikipedia.org/wiki/%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%B0%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D1%8B основной теореме алгебры], полином имеет ровно <tex> d </tex> корней, и <tex> r_i \in \lbrace 0, \ldots, p -1 \rbrace</tex>.
+::;'''Шаг m'''
-:<tex>\ldots</tex>
+:::Так как на последнем шаге <tex>V</tex> сверяет полученное от <tex>P</tex> значение с непосредственно вычисленным, слово будет допущено только в том случае, когда <tex>P</tex> смог прислать верное значение, что в свою очередь возможно лишь если на одном из предыдущих шагов был верно угадан корень полинома.
 :'''Шаг m'''
-:Так как на последнем шаге <tex>V</tex> сверяет полученное от <tex>P</tex> значение с непосредственно вычисленным, слово будет допущено только в том случае, когда <tex>P</tex> смог прислать верное значение, что в свою очередь возможно лишь если на одном из предыдущих шагов был верно угадан корень полинома.
+:::Вычислим вероятность того, что хотя бы раз корень был угадан.
+:::<tex>\mathbb{P}(V_{P}(\langle \varphi, k \rangle)=1) = 1 - \left( 1 - \dfrac{d}{p} \right)^m \leqslant 1 - \left(1 - \dfrac{d}{3dm}\right)^m = 1 - \left(1 - \dfrac{1}{3m}\right)^m  </tex>.
-:Вычислим вероятность того, что хотя бы раз корень был угадан.
+:::Заметим, что функция <tex> y(m) = 1 - \left( 1 - \dfrac{1}{3m} \right)^{m}</tex> убывает при <tex> m \geqslant \dfrac{1}{3} </tex>. А так как <tex> m \geqslant 1 </tex> и <tex> y(1) = \dfrac{1}{3} </tex>, в итоге получаем, что <tex>\mathbb{P}(V_{P}(\langle \varphi, k \rangle)=1) \leqslant \dfrac{1}{3} </tex>.
 Таким образом, построенный нами интерактивный протокол корректен, а значит лемма доказана.
 }}
 {{Теорема
@@ Строка 81: / Строка 82: @@
 [[Сведение_относительно_класса_функций._Сведение_по_Карпу._Трудные_и_полные_задачи|Сведём]] [[Теорема_Бермана_—_Форчуна | язык <tex>\mathrm{TAUT}</tex>]] к языку <tex>\mathrm{\#SAT}</tex> следующим образом: <tex>\varphi \mapsto \langle \varphi, 2^k \rangle </tex>, где <tex>k</tex> — количество различных переменных в формуле <tex>\varphi</tex>.
-Очевидно, что <tex>\varphi \in \mathrm{TAUT} \Leftrightarrow \langle \varphi, 2^k \rangle \in \mathrm{\#SAT}</tex>.
+<tex>\varphi \in \mathrm{TAUT} \Leftrightarrow \forall x = (x_1, \ldots, x_k) \varphi(x) = 1 \Leftrightarrow \exists 2^{k} </tex> удовлетворяющих наборов <tex> x </tex> для <tex> \varphi(x) \Leftrightarrow \langle \varphi, 2^k \rangle \in \mathrm{\#SAT}</tex>.
 По лемме (2) <tex>\mathrm{\#SAT} \in \mathrm{IP}</tex>. Тогда <tex>\mathrm{TAUT} \in \mathrm{IP}</tex>. Так как <tex>\mathrm{TAUT} \in \mathrm{coNPC}</tex>, то <tex>\mathrm{coNP} \subset \mathrm{IP}</tex>.
@@ Строка 91: / Строка 92: @@
 * [[Теорема Бермана — Форчуна]]
 * [[Классы NP, coNP, Σ₁, Π₁]]
 [[Категория: Теория сложности]]
 [[Категория: Вероятностные сложностные классы]]
 [[Категория: Интерактивные протоколы]]

@@ Строка 16: / Строка 16: @@
 |statement=<tex>\mathrm{\#SAT} \in \mathrm{IP}</tex>.
 |proof=
 Сперва арифметизуем формулу <tex>\varphi</tex>. Пусть полученный полином <tex>A_\varphi(x_1, x_2, \ldots, x_m)</tex> имеет степень <tex>d</tex>.
-По лемме (1) вместо условия <tex>\langle \varphi, k \rangle \in \mathrm{\#SAT}</tex>, можно проверять условие <tex>\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1  A_\varphi(x_1, \ldots, x_m)=k</tex>.
+Для доказательства леммы построим программы <tex>V</tex> (<tex> \mathrm{Verifier}</tex>) и <tex>P</tex> (<tex>\mathrm{Prover}</tex>) из [[Интерактивные протоколы. Класс IP. Класс AM#Класс IP|определения]] класса <tex>\mathrm{IP}</tex>.
 Приступим к описанию [[Интерактивные протоколы. Класс IP. Класс AM|интерактивного протокола]].
-'''Шаг 0'''
+; '''Шаг 0'''
+:Если <tex>d=0</tex> или <tex>m=0</tex>, то <tex>V</tex> может проверить указанное выше условие сам и вернуть соответствующий результат. Иначе запросим у <tex>P</tex> такое простое число <tex>p</tex>, что <tex>3dm \leqslant p \leqslant 6dm</tex> (такое <tex>p</tex> существует в силу [http://ru.wikipedia.org/wiki/Постулат_Бертрана постулата Бертрана]). Проверим <tex>p</tex> на простоту и на принадлежность заданному промежутку. Как мы [[Класс P#Примеры задач и языков из P|знаем]], <tex>\mathrm{Primes} \in \mathrm{P}</tex>, следовательно на эти операции у <tex>V</tex> уйдёт полиномиальное от размера входа время.
-Пусть <tex>r_i = \mathrm{random} \lbrace0, \ldots, p-1 \rbrace</tex>. Отправим <tex>r_i</tex> программе <tex>P</tex>.
+:Далее будем проводить все вычисления по модулю <tex>p</tex>, то есть над конечным полем <tex> \mathbb{F}_{p} </tex>, что не позволяет числам становиться слишком большими и упрощает анализ.
-Попросим <tex>P</tex> прислать <tex>V</tex> формулу <tex>A_i(x_{i+1}) = \sum\limits_{x_{i+2} = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A_\varphi(r_1,\ldots, r_i, x_{i+1}, \ldots, x_m)</tex>.
+:Попросим <tex>P</tex> прислать <tex>V</tex> формулу <tex>A_0(x_1)= \sum\limits_{x_2 = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A_\varphi(x_1, x_2, \ldots, x_m)</tex>. Заметим, что размер формулы <tex>A_0(x_1)</tex> будет полином от длины входа <tex>V</tex>, так как <tex>A_0(x_1)</tex> — полином степени не выше, чем <tex>d</tex>, от одной переменной, а значит его можно представить в виде <tex>A_0(x) = \sum\limits_{i = 0}^{d} C_i \cdot x ^ i</tex>.
-Проверим следующее утверждение: <tex>A_i(0) + A_i(1) = A_{i-1}(r_i)</tex> (*).
+:Проверим следующее утверждение: <tex>A_0(0) + A_0(1) = k</tex> (*) (здесь и далее под словом «проверим» будем подразумевать следующее: если утверждение верно, <tex>V</tex> продолжает свою работу, иначе он прекращает свою работу и возвращет '''false''').
-'''Шаг m'''
+; '''Шаг i'''
-Пусть <tex>r_m = \mathrm{random} \lbrace0, \ldots, p-1 \rbrace</tex>. Отправим <tex>r_m</tex> программе <tex>P</tex>.
+:Попросим <tex>P</tex> прислать <tex>V</tex> формулу <tex>A_i(x_{i+1}) = \sum\limits_{x_{i+2} = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A_\varphi(r_1,\ldots, r_i, x_{i+1}, \ldots, x_m)</tex>.
-Попросим программу <tex>P</tex> прислать <tex>V</tex> значение <tex>A_m()= A_\varphi(r_1, r_2, \ldots, r_m)</tex>.
+:Проверим следующее утверждение: <tex>A_i(0) + A_i(1) = A_{i-1}(r_i)</tex> (*).
-Проверим следующее утверждение: <tex>A_m() = A_{m-1}(r_m)</tex> (*).
+:Попросим программу <tex>P</tex> прислать <tex>V</tex> значение <tex>A_m()= A_\varphi(r_1, r_2, \ldots, r_m)</tex>.
-Возвращаем '''true'''.
+:Проверим следующее утверждение: <tex>A_m() = A_{m-1}(r_m)</tex> (*). А также сами подставим <tex>r_1, r_2, \ldots, r_m</tex> в <tex>A_\varphi(x_1, x_2, \ldots, x_m)</tex> и проверим правильность присланного значения <tex>A_m()</tex>.
 Докажем теперь, что построенный таким образом интерактивны протокол — корректный. Для этого нужно доказать следующие утверждения:
 # Построенный <tex>V</tex> - [[Вероятностные_вычисления._Вероятностная_машина_Тьюринга|вероятностная машина Тьюринга]], совершающая не более полинома от длины входа действий.

@@ Строка 1: / Строка 1: @@
 {{Определение
 |definition=
-<tex>\mathrm{\#SAT}=\{\langle \varphi, k \rangle \mid \varphi</tex> имеет ровно <tex>k</tex> удовлетворяющих наборов <tex>\}</tex>.
+<tex>\mathrm{\#SAT}=\{\langle \varphi, k \rangle \mid \varphi</tex> {{---}} [[Определение_булевой_функции | булева формула]], которая имеет ровно <tex>k</tex> удовлетворяющих наборов <tex>\}</tex>.
 }}
@@ Строка 7: / Строка 7: @@
 {{Лемма
 |about=1
-|statement=<tex>\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1  A_\varphi(x_1, \ldots, x_m)=k \Leftrightarrow \langle \varphi,k\rangle \in \mathrm{\#SAT}</tex>.
+|statement=Пусть <tex> \varphi </tex> булева формула, а <tex> A_\varphi </tex> {{---}} её [[Арифметизация булевых формул с кванторами|арифметизация]]. Тогда <tex>\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1  A_\varphi(x_1, \ldots, x_m)=k \Leftrightarrow \langle \varphi,k\rangle \in \mathrm{\#SAT}</tex>.
 |proof=Следует из [[Арифметизация булевых формул с кванторами | леммы (1)]].
 }}
@@ Строка 18: / Строка 18: @@
 Для доказательства леммы построим программы <tex>V</tex> (<tex> \mathit{Verifier}</tex>) и <tex>P</tex> (<tex>\mathit{Prover}</tex>) из [[Интерактивные протоколы. Класс IP. Класс AM#Класс IP|определения]] класса <tex>\mathrm{IP}</tex>.
-Сперва [[Арифметизация булевых формул с кванторами|арифметизуем]] формулу <tex>\varphi</tex>. Пусть полученный полином <tex>A(x_1, x_2, \ldots, x_m)</tex> имеет степень <tex>d</tex>.
+Сперва арифметизуем формулу <tex>\varphi</tex>. Пусть полученный полином <tex>A_\varphi(x_1, x_2, \ldots, x_m)</tex> имеет степень <tex>d</tex>.
-По лемме (1) вместо условия <tex>\langle \varphi, k \rangle \in \mathrm{\#SAT}</tex>, можно проверять условие <tex>\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1  A(x_1, \ldots, x_m)=k</tex>.
+По лемме (1) вместо условия <tex>\langle \varphi, k \rangle \in \mathrm{\#SAT}</tex>, можно проверять условие <tex>\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1  A_\varphi(x_1, \ldots, x_m)=k</tex>.
 Приступим к описанию [[Интерактивные протоколы. Класс IP. Класс AM|интерактивного протокола]].
@@ Строка 32: / Строка 32: @@
 Далее будем проводить все вычисления модулю <tex>p</tex>, то есть над конечным полем <tex> \mathbb{F}_{p} </tex>, что не позволяет числам становиться слишком большими и упрощает анализ.
-Попросим <tex>P</tex> прислать <tex>V</tex> формулу <tex>A_0(x_1)= \sum\limits_{x_2 = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A(x_1, x_2, \ldots, x_m)</tex>.
+Попросим <tex>P</tex> прислать <tex>V</tex> формулу <tex>A_0(x_1)= \sum\limits_{x_2 = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A_\varphi(x_1, x_2, \ldots, x_m)</tex>.
 Заметим, что размер формулы <tex>A_0(x_1)</tex> будет полином от длины входа <tex>V</tex>, так как <tex>A_0(x_1)</tex> — полином степени не выше, чем <tex>d</tex>, от одной переменной, а значит его можно представить в виде <tex>A_0(x) = \sum\limits_{i = 0}^{d} C_i \cdot x ^ i</tex>.
@@ Строка 41: / Строка 41: @@
 Пусть <tex>r_i = \mathrm{random} \lbrace0, \ldots, p-1 \rbrace</tex>. Отправим <tex>r_i</tex> программе <tex>P</tex>.
-Попросим <tex>P</tex> прислать <tex>V</tex> формулу <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}, \ldots, x_m)</tex>.
+Попросим <tex>P</tex> прислать <tex>V</tex> формулу <tex>A_i(x_{i+1}) = \sum\limits_{x_{i+2} = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A_\varphi(r_1,\ldots, r_i, x_{i+1}, \ldots, x_m)</tex>.
 Проверим следующее утверждение: <tex>A_i(0) + A_i(1) = A_{i-1}(r_i)</tex> (*).
@@ Строка 49: / Строка 49: @@
 Пусть <tex>r_m = \mathrm{random} \lbrace0, \ldots, p-1 \rbrace</tex>. Отправим <tex>r_m</tex> программе <tex>P</tex>.
-Попросим программу <tex>P</tex> прислать <tex>V</tex> значение <tex>A_m()= A(r_1, r_2, \ldots, r_m)</tex>.
+Попросим программу <tex>P</tex> прислать <tex>V</tex> значение <tex>A_m()= A_\varphi(r_1, r_2, \ldots, r_m)</tex>.
 Проверим следующее утверждение: <tex>A_m() = A_{m-1}(r_m)</tex> (*).
-А также сами подставим <tex>r_1, r_2, \ldots, r_m</tex> в <tex>A(x_1, x_2, \ldots, x_m)</tex> и проверим правильность присланного значения <tex>A_m()</tex>.
+А также сами подставим <tex>r_1, r_2, \ldots, r_m</tex> в <tex>A_\varphi(x_1, x_2, \ldots, x_m)</tex> и проверим правильность присланного значения <tex>A_m()</tex>.
 Возвращаем '''true'''.
@@ Строка 67: / Строка 67: @@
 #Пусть количество наборов, удовлетворяющих <tex>\varphi</tex>, не равно <tex>k</tex>. Для того, чтобы <tex>V</tex> вернул '''true''', <tex>P</tex> должен посылать такие <tex>A_i</tex>, чтобы выполнялись все проверяемые условия. Посмотрим на то, что он может послать:
 :'''Шаг 0'''
-:Так как количество наборов, удовлетворяющих <tex>\varphi</tex>, не равно <tex>k</tex>, то <tex>\mathit{Prover}</tex> не может послать правильное <tex>A_0</tex>, поскольку в этом случае не выполнится условие <tex>A_0(0) + A_0(1) = k</tex>. Поэтому он посылает не <tex>A_0</tex>, а некое <tex>\tilde{A}_0</tex>.
+:Так как количество наборов, удовлетворяющих <tex>\varphi</tex>, не равно <tex>k</tex>, то <tex>P</tex> не может послать правильное <tex>A_0</tex>, поскольку в этом случае не выполнится условие <tex>A_0(0) + A_0(1) = k</tex>. Поэтому он посылает не <tex>A_0</tex>, а некое <tex>\tilde{A}_0</tex>.
 :<tex>\ldots</tex>
 :'''Шаг i'''
@@ Строка 87: / Строка 87: @@
 |statement=<tex>\mathrm{coNP} \subset \mathrm{IP}</tex>.
 |proof=
-Сведём [[Теорема_Бермана_—_Форчуна | язык <tex>\mathrm{TAUT}</tex>]] к языку <tex>\mathrm{\#SAT}</tex> следующим образом: <tex>\varphi \mapsto \langle \varphi, 2^k \rangle </tex>, где <tex>k</tex> — количество различных переменных в формуле <tex>\varphi</tex>.
+[[Сведение_относительно_класса_функций._Сведение_по_Карпу._Трудные_и_полные_задачи|Сведём]] [[Теорема_Бермана_—_Форчуна | язык <tex>\mathrm{TAUT}</tex>]] к языку <tex>\mathrm{\#SAT}</tex> следующим образом: <tex>\varphi \mapsto \langle \varphi, 2^k \rangle </tex>, где <tex>k</tex> — количество различных переменных в формуле <tex>\varphi</tex>.
 Очевидно, что <tex>\varphi \in \mathrm{TAUT} \Leftrightarrow \langle \varphi, 2^k \rangle \in \mathrm{\#SAT}</tex>.
@@ Строка 98: / Строка 98: @@
 * [[Вероятностные вычисления. Вероятностная машина Тьюринга]]
 * [[Теорема Бермана — Форчуна]]
 [[Категория: Теория сложности]]
 [[Категория: Вероятностные сложностные классы]]
 [[Категория: Интерактивные протоколы]]