Классы BPP и PP - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:26:48Z

rollbackEdits.php mass rollback

91.212.153.123 в 04:45, 1 сентября 2022

2022-09-01T04:45:03Z

Infovarius: кат

2018-11-14T13:04:20Z

кат

Dgerasimov в 14:40, 5 июня 2013

2013-06-05T14:40:21Z

Igor buzhinsky: /* Определения */

2012-06-04T21:17:38Z

‎Определения

Andrey.Eremeev: переименовал Класс BPP в Классы BPP и PP

2012-06-04T20:50:24Z

переименовал Класс BPP в Классы BPP и PP

Igor buzhinsky: /* Теорема */

2012-06-04T20:48:20Z

‎Теорема

Andrey.Eremeev: /* Определения */

2012-06-04T20:32:12Z

‎Определения

Andrey.Eremeev в 20:14, 4 июня 2012

2012-06-04T20:14:02Z

Igor buzhinsky: Здесь будет новая статья

2012-06-04T19:34:15Z

Здесь будет новая статья

← Предыдущая		Версия 16:26, 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 Майкл Наки].
−	\|}
−
	==Определения==		==Определения==
	{{Определение		{{Определение

← Предыдущая		Версия 04:45, 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 Майкл Наки].
		+	\|}
		+
	==Определения==		==Определения==
	{{Определение		{{Определение

← Предыдущая		Версия 13:04, 14 ноября 2018
Строка 55:		Строка 55:
	* [http://en.wikipedia.org/wiki/Bounded-error_probabilistic_polynomial Wikipedia — BPP complexity class]		* [http://en.wikipedia.org/wiki/Bounded-error_probabilistic_polynomial Wikipedia — BPP complexity class]

−	[[Категория: Теория ~~сложности~~]]	+	[[Категория:Классы сложности]]
		+	[[Категория:Теория формальных языков]]

@@ Строка 52: / Строка 52: @@
 * [[Вероятностные вычисления. Вероятностная машина Тьюринга]] <br>
 * [http://en.wikipedia.org/wiki/Chernoff_bound Неравенство Чернова]
 [[Категория: Теория сложности]]

@@ Строка 6: / Строка 6: @@
 # <tex>T(p, x) \le poly(|x|)</tex> для любой [[Вероятностные вычисления. Вероятностная машина Тьюринга |вероятностной ленты]].
 }}
 {{Определение
@@ Строка 15: / Строка 17: @@
 <tex>\mathrm{PP}</tex> также допускает двусторонние ошибки, но является более широким по сравнению с <tex>\mathrm{BPP}</tex>.
 {{Определение

← Предыдущая	Версия 20:50, 4 июня 2012
(нет различий)

@@ Строка 47: / Строка 47: @@
 # <tex>\mathrm{BPP_{strong}} \subseteq \mathrm{BPP} </tex> <br> Это следует из определений <tex>\mathrm{BPP}</tex> и <tex>\mathrm{BPP_{strong}}</tex>.
 # <tex>\mathrm{BPP} \subseteq \mathrm{BPP_{strong}}</tex> <br> Пусть <tex>L \in \mathrm{BPP}</tex>. Тогда <tex>\exists p : P(p(x)=[x \in L]) \ge \frac {2}{3}</tex>. <br> Построим ВМТ <tex>p_1</tex>, которая для входа <tex>x</tex> запускает <tex>p(x)</tex> <tex>n</tex> раз, и принимает <tex>x</tex>, если больше половины запусков принимают его. <br> Подберем <tex>n</tex>, такое, что <tex>P(p_1(x)=[x \in L]) \ge 1 - \frac {1}{2^{q(|x|)}}</tex> и <tex>T(p_1(x)) \le poly(|x|)</tex>. <br> Проводя рассуждения, аналогичные изложенным в доказательстве <tex>\mathrm{BPP_{weak}} \subseteq \mathrm{BPP}</tex>, получаем, что <tex>1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} \ge 1 - \frac {1}{2^{q(|x|)}}</tex>, где <tex>p = \frac {2} {3}</tex>. Отсюда <tex>n \ge \frac {{q(|x|)} \ln 2}{2({\frac {2}{3} - \frac {1}{2}})^2} </tex>. Возьмем <tex>n = \lceil 18 {q(|x|)} \ln 2 \rceil </tex>, тогда неравенство <tex>T(p_1(x)) \le poly(|x|)</tex> будет выполнено.
 }}

← Предыдущая		Версия 20:14, 4 июня 2012
Строка 1:		Строка 1:
−	{{~~В разработке~~}}	+	==Определения==
		+	{{Определение
		+	\|definition =
		+	<tex>\mathrm{BPP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых существует такая [[Вероятностные вычисления. Вероятностная машина Тьюринга \|ВМТ]] <tex>p</tex>, что для любого <tex>x</tex>:
		+	# <tex>P(p(x) = [x \in L]) \ge 2/3</tex>;
		+	# <tex>T(p, x) \le poly(\|x\|)</tex> для любой [[Вероятностные вычисления. Вероятностная машина Тьюринга \|вероятностной ленты]].
		+	}}

−	~~Здесь~~ будет ~~статья~~.	+	<tex>\mathrm{BPP}</tex> — сложностный класс, допускающий двусторонние ошибки.
		+	Константу <tex>2/3</tex> можно заменить на любое число из промежутка <tex>(1/2, 1)</tex>, так как требуемой вероятности можно добиться множественным запуском <tex>p</tex>. Замена константы на <tex>1/2</tex> сделала бы данный класс равным <tex>\Sigma^*</tex> (программа, возвращающая результат функции ''random''(), подошла бы для любого языка).
		+
		+	{{Определение
		+	\|definition=
		+	<tex>\mathrm{BPP_{weak}}</tex> — класс языков <tex>L</tex>, для которых существует такая ВМТ <tex>p</tex>, что для любого <tex>x</tex>:
		+	#<tex>P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(\|x\|)}</tex>, где <tex>q</tex>-полином и <tex>q(\|x\|) \ge 3</tex>;
		+	#<tex>T(p, x) \le poly(\|x\|)</tex> для любой вероятностной ленты.
		+	}}
		+
		+	{{Определение
		+	\|definition=
		+	<tex>\mathrm{BPP_{strong}}</tex> — класс языков <tex>L</tex>, для которых существует такая ВМТ <tex>p</tex>, что для любого <tex>x</tex>:
		+	#<tex>P(p(x)=[x \in L]) \ge 1 - \frac {1} {2^{q(\|x\|)}}</tex>, где <tex>q</tex>-полином и <tex>q(\|x\|) \ge 3</tex>;
		+	#<tex>T(p, x) \le poly(\|x\|)</tex> для любой вероятностной ленты.
		+	}}
		+
		+	==Теорема==
		+	{{Теорема
		+	\|statement= <tex>\mathrm{BPP} = \mathrm{BPP_{weak}} = \mathrm{BPP_{strong}}</tex>.
		+	\|proof=
		+	В доказательстве будет использоваться ''неравенство Чернова'': <br>
		+	<tex>\forall p : \frac {1} {2} \le p \le 1: \sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}^n \binom{n}{i}p^i (1 - p)^{n - i} \ge 1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2}</tex>
		+
		+
		+	* Докажем, что <tex>\mathrm{BPP} = \mathrm{BPP_{weak}}</tex>
		+	# <tex>\mathrm{BPP} \subseteq \mathrm{BPP_{weak}}</tex> <br> Это следует из определений <tex>\mathrm{BPP}</tex> и <tex>\mathrm{BPP_{weak}}</tex>.
		+	# <tex>\mathrm{BPP_{weak}} \subseteq \mathrm{BPP}</tex> <br> Пусть <tex>L \in \mathrm{BPP_{weak}}</tex>. Тогда <tex>\exists p : P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(\|x\|)}</tex>. <br> Построим ВМТ <tex>p_1</tex>, которая для входа <tex>x</tex> запускает <tex>p(x)</tex> <tex>n</tex> раз, и принимает <tex>x</tex>, если больше половины запусков принимают его. <br> Подберем <tex>n</tex>, такое, что <tex>P(p_1(x)=[x \in L]) \ge \frac {2}{3}</tex> и <tex>T(p_1(x)) \le poly(\|x\|)</tex>. <br> Вероятность <tex>P</tex> того, что <tex>p_1(x)</tex> даст правильный результат равна вероятности, что больше половины запусков <tex>p(x)</tex> дадут правильный результат. Тогда по схеме Бернулли <tex>P = \sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}^n \binom{n}{i}p^i (1 - p)^{n - i}</tex>, где <tex>p=\frac {1}{2} + \frac {1} {q(\|x\|)}</tex> — вероятность, что запуск <tex>p(x)</tex> даст правильный ответ. По неравенству Чернова : <tex> P \ge 1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} </tex>. То есть для того, чтобы <tex>P(p(x)=[x \in L]) \ge \frac {2}{3}</tex> достаточно подобрать такое <tex>n</tex>, что <tex>1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} \ge \frac {2}{3}</tex>. Получаем, что <tex>n \ge \frac {\ln 3} {2(p - \frac {1} {2})^2} = \frac {{q(\|x\|)}^2 \ln 3}{2} </tex>. Возьмем <tex>n = \lceil \frac {{q(\|x\|)}^2 \ln 3}{2} \rceil </tex>, тогда неравенство <tex>T(p_1(x)) \le poly(\|x\|)</tex> будет выполнено.
		+
		+	* Докажем, что <tex>\mathrm{BPP} = \mathrm{BPP_{strong}}</tex>
		+	# <tex>\mathrm{BPP_{strong}} \subseteq \mathrm{BPP} </tex> <br> Это следует из определений <tex>\mathrm{BPP}</tex> и <tex>\mathrm{BPP_{strong}}</tex>.
		+	# <tex>\mathrm{BPP} \subseteq \mathrm{BPP_{strong}}</tex> <br> Пусть <tex>L \in \mathrm{BPP}</tex>. Тогда <tex>\exists p : P(p(x)=[x \in L]) \ge \frac {2}{3}</tex>. <br> Построим ВМТ <tex>p_1</tex>, которая для входа <tex>x</tex> запускает <tex>p(x)</tex> <tex>n</tex> раз, и принимает <tex>x</tex>, если больше половины запусков принимают его. <br> Подберем <tex>n</tex>, такое, что <tex>P(p_1(x)=[x \in L]) \ge 1 - \frac {1}{2^{q(\|x\|)}}</tex> и <tex>T(p_1(x)) \le poly(\|x\|)</tex>. <br> Проводя рассуждения, аналогичные изложенным в доказательстве <tex>\mathrm{BPP_{weak}} \subseteq \mathrm{BPP}</tex>, получаем, что <tex>1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} \ge 1 - \frac {1}{2^{q(\|x\|)}}</tex>, где <tex>p = \frac {2} {3}</tex>. Отсюда <tex>n \ge \frac {{q(\|x\|)} \ln 2}{2({\frac {2}{3} - \frac {1}{2}})^2} </tex>. Возьмем <tex>n = \lceil 18 {q(\|x\|)} \ln 2 \rceil </tex>, тогда неравенство <tex>T(p_1(x)) \le poly(\|x\|)</tex> будет выполнено.
		+	}}
		+
		+	{{Теорема
		+	\|statement =
		+	<tex>\mathrm{RP} \cup \mathrm{coRP} \subset \mathrm{BPP}</tex>.
		+	\|proof =
		+	Пусть <tex>p</tex> — программа для <tex>L \in \mathrm{RP}</tex>. Программу <tex>q</tex> для <tex>\mathrm{BPP}</tex> определим следующим образом:
		+	<tex>q</tex>(x)
		+	u <- <tex>p</tex>(x)
		+	v <- <tex>p</tex>(x)
		+	'''return''' u '''or''' v
		+	Пусть <tex>x \in L</tex>. В этом случае вероятность ошибки равна <tex>\operatorname{P}(u = 0, v = 0) = \operatorname{P}(u = 0) \cdot \operatorname{P}(v = 0) \le 1/4</tex>.
		+
		+	Пусть <tex>x \notin L</tex>. Тогда с вероятностью <tex>1</tex> будет верно <tex>u = 0, v = 0</tex> и <tex>q</tex> вернет правильный ответ.
		+
		+	Аналогично доказывается, что <tex>\mathrm{coRP} \subset \mathrm{BPP}</tex>.
		+	}}
		+
		+	== См. также ==
		+	* [[Вероятностные вычисления. Вероятностная машина Тьюринга]] <br>
		+	* [http://en.wikipedia.org/wiki/Chernoff_bound Неравенство Чернова]
		+
		+	[[Категория: Теория сложности]]

← Предыдущая		Версия 19:34, 4 июня 2012
Строка 1:		Строка 1:
−	~~===Определения===~~	+	{{В разработке}}
−	~~<math>BPP = \~~{~~L \|~~{ }~~\exist m: T(m,x) = Poly(\|x\|) \and P(m(x) = [x \in L]) > 2/3\~~}~~</math><br>~~
−	~~где <math>m</math> -- [[Вероятностная машина Тьюринга\|вероятностная машина Тьюринга]].<br>~~
−	~~Существуют альтернативные определения класса <math>BPP</math>:<br>~~
−	*<math>BPP_{weak} = \{L \|{ }\exist m: T(m,x) = Poly(\|x\|) \and P(m(x) = [x \in L]) > 1/2 + 1/p(\|x\|)\}</math><br>
−	~~где <math>m</math> -- [[Вероятностная машина Тьюринга\|ВМТ]], а <math>~p(\|x\|): \forall x: p(\|x\|) > 2</math> -- полином.~~
−	*<math>BPP_{strong} = \{L \|{ }\exist m: T(m,x) = Poly(\|x\|) \and P(m(x) = [x \in L]) > 1 - 2^{-p(\|x\|)}\}</math><br>
−	~~где <math>m</math> -- [[Вероятностная машина Тьюринга\|ВМТ]], а <math>~p(\|x\|)</math> -- полином.~~

−	~~===Эквивалентность определений===~~	+	Здесь будет статья.
−	~~Требуется доказать, что <math>~BPP_{strong} = BPP= BPP_{weak}</math>.<br>~~
−	~~Для доказательства обоих равенств потребуется неравенство Чернова:<br>~~
−	~~<center><math>\forall p > 1/2:~ \sum_{\mathcal{b}\frac{n}{2}\mathcal{c}+1}^{n}[{{{n\choose i}} p^{i}(1-p)^{n-i}] \geq 1 - e^{-2n(p-1/2)^2}}</math></center>~~
−
−	~~====Доказательство <math>~BPP_{strong} = BPP</math>====~~
−	~~Очевидно, что <math>~BPP_{strong} \subset BPP</math>.<br>~~
−	~~Докажем обратное включение. Пусть <math>L \in BPP</math>, тогда существует~~
−	[[Вероятностная машина Тьюринга\|ВМТ]] <math>m_{1}: T(m_{1},x) = Poly(\|x\|) \and P(m_{1}(x) = [x \in L]) > 2/3</math>. Построим [[Вероятностная машина Тьюринга\|ВМТ]] <math>m_{2}: T(m_{2},x) = Poly(\|x\|) \and P(m_{2}(x) = [x \in L]) >1 - 2^{-p(\|x\|)}</math>,
−	используя заданные <math>m_{1}</math> и <math>~p(\|x\|)</math>. Если нам это удастся, то <math>L \in BPP_{strong} \Rightarrow BPP \in BPP_{strong} \Rightarrow ~BPP_{strong} = BPP</math>.
−	~~=====Построение <math>~m_{2}</math>=====~~
−	~~Машина <math>m_{2}</math>~~ будет ~~работать таким образом:~~
−	~~запустим <math>~N_{str}(p(\|x\|),m_{1})</math> раз машину <math>m_{1}</math>, запоминая результат каждого запуска.~~
−	~~Вернем <math>1</math>, если больше половины запусков вернули <math>1</math>. Иначе вернем <math>0</math>.~~
−	~~Если <math>N_{str}</math> таково, что <math>P(m_{2}(x) = [x \in L]) >1 - 2^{-p(\|x\|)} \and N_{str} \in poly(\|x\|)</math>, то искомая машина построена.~~
−	~~======Построение <math>~N_{str}(p\|x\|,m_{1})</math>======~~
−	~~При запуске машины <math>m_{2}</math> все запуски <math>m_{1}</math> можно считать независимыми, причем каждый запуск~~
−	<math>m_{1}</math> возвращает правильный ответ с вероятностью <math>p \geq 2/3 > 1/2</math>. Тогда по схеме Бернулли вероятность того, что больше половины запусков вернули правильный ответ, т.е <math>P(m_{2}(x) = [x \in L])</math>:<br>
−	<math>P(m_{2}(x) = [x \in L]) = \sum_{\mathcal{b}\frac{N_{str}}{2}\mathcal{c}+1}^{N_{str}}[{N_{str}\choose i} p^{i}(1-p)^{N_{str}-i}]</math>. Тогда, по неравенству Чернова: <math>P(m_{2}(x) = [x \in L]) \geq 1 - e^{-2N_{str}(p-1/2)^2}</math>. Достаточно подобрать такое <math>N_{str}</math>, чтобы <math>1 - e^{-2N_{str}(p-1/2)^2} \geq 1 - 2^{-p(\|x\|)}</math>. Несложными преобразованиями получаем <math>N_{str} \geq \frac{p(\|x\|) \ln 2}{2(p-1/2)^2}</math>, т.е. можем выбрать <math>N_{str} \in poly(\|x\|)</math>
−
−
−	~~====Доказательство <math>~BPP_{weak} = BPP</math>====~~
−	~~Очевидно, что <math>~BPP \subset BPP_{weak}</math>.<br>~~
−	~~Докажем обратное включение. Пусть <math>L \in BPP_{weak}</math>, тогда существует~~
−	[[Вероятностная машина Тьюринга\|ВМТ]] <math>m_{1}: T(m_{1},x) = Poly(\|x\|) \and P(m_{1}(x) = [x \in L]) > 1/2 + 1/p(\|x\|)</math>. Построим [[Вероятностная машина Тьюринга\|ВМТ]] <math>m_{2}: T(m_{2},x) = Poly(\|x\|) \and P(m_{2}(x) = [x \in L]) >2/3</math>,
−	используя заданные <math>m_{1}</math> и <math>~p(\|x\|)</math>. Если нам это удастся, то <math>L \in BPP \Rightarrow BPP_{weak} \in BPP \Rightarrow ~BPP_{weak} = BPP</math>.
−	~~=====Построение <math>~m_{2}</math>=====~~
−	~~Машина <math>m_{2}</math> будет работать таким образом:~~
−	~~запустим <math>~N_{str}(p(\|x\|),m_{1})</math> раз машину <math>m_{1}</math>, запоминая результат каждого запуска.~~
−	~~Вернем <math>1</math>, если больше половины запусков вернули <math>1</math>. Иначе вернем <math>0</math>.~~
−	~~Если <math>N_{weak}</math> таково, что <math>P(m_{2}(x) = [x \in L]) > 2/3) \and N_{weak} \in poly(\|x\|)</math>, то искомая машина построена.~~
−	~~======Построение <math>~N_{weak}(p\|x\|,m_{1})</math>======~~
−	~~При запуске машины <math>m_{2}</math> все запуски <math>m_{1}</math> можно считать независимыми, причем каждый запуск~~
−	<math>m_{1}</math> возвращает правильный ответ с вероятностью <math>p = 1/2 + 1/p(\|x\|) > 1/2</math>. Тогда по схеме Бернулли вероятность того, что больше половины запусков вернули правильный ответ, т.е <math>P(m_{2}(x) = [x \in L])</math>:<br>
−	<math>P(m_{2}(x) = [x \in L]) = \sum_{\mathcal{b}\frac{N_{weak}}{2}\mathcal{c}+1}^{N_{weak}}[{N_{weak}\choose i} p^{i}(1-p)^{N_{weak}-i}]</math>. Тогда, по неравенству Чернова: <math>P(m_{2}(x) = [x \in L]) \geq 1 - e^{-2N_{weak}(p-1/2)^2}</math>. Достаточно подобрать такое <math>N_{weak}</math>, чтобы <math>1 - e^{-2N_{weak}(p-1/2)^2} \geq 2/3</math>. Несложными преобразованиями получаем <math>N_{weak} \geq \frac{\ln 3}{2(1/2 +1/p(\|x\|)-1/2)^2} = \frac{p(\|x\|)^2 \ln 3}{2}</math>, т.е. можем выбрать <math>N_{weak} \in poly(\|x\|)</math>.