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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:33:38Z

rollbackEdits.php mass rollback

88.208.225.209 в 04:16, 1 сентября 2022

2022-09-01T04:16:01Z

Infovarius: кат

2018-11-14T13:03:50Z

кат

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

2012-06-04T20:09:00Z

переименовал Классы BPP, BPPweak и BPPstrong в Классы BPP

Igor buzhinsky в 20:07, 4 июня 2012

2012-06-04T20:07:07Z

Igor buzhinsky: переименовал Классы BPPweak и BPPstrong в Классы BPP, BPPweak и BPPstrong: Объединяем с BPP

2012-06-04T19:49:47Z

переименовал Классы BPPweak и BPPstrong в Классы BPP, BPPweak и BPPstrong: Объединяем с BPP

Shevchen в 19:26, 4 июня 2012

2012-06-04T19:26:40Z

Petrova.Irina: /* Определения */

2012-06-04T19:21:16Z

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

Berezhkovskaya в 18:44, 4 июня 2012

2012-06-04T18:44:39Z

Petrova.Irina: /* См. также */

2012-06-04T18:42:21Z

‎См. также

← Предыдущая		Версия 16:33, 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:16, 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:03, 14 ноября 2018
Строка 61:		Строка 61:
	* [http://en.wikipedia.org/wiki/Chernoff_bound Неравенство Чернова]		* [http://en.wikipedia.org/wiki/Chernoff_bound Неравенство Чернова]

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

@@ Строка 4: / Строка 4: @@
 <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>T(p, x) \le poly(|x|)</tex> для любой [[Вероятностные вычисления. Вероятностная машина Тьюринга |вероятностной ленты]].
 }}
@@ Строка 14: / Строка 14: @@
 <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> для любой вероятностной ленты.
+#<tex>T(p, x) \le poly(|x|)</tex> для любой вероятностной ленты.
 }}
@@ Строка 21: / Строка 21: @@
 <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> для любой вероятностной ленты.
+#<tex>T(p, x) \le poly(|x|)</tex> для любой вероятностной ленты.
 }}
@@ Строка 39: / Строка 39: @@
 # <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> будет выполнено.
 }}
 == См. также ==
-[[Вероятностные вычисления. Вероятностная машина Тьюринга]] <br>
+* [[Вероятностные вычисления. Вероятностная машина Тьюринга]] <br>
-[http://en.wikipedia.org/wiki/Chernoff_bound Неравенство Чернова]
+* [http://en.wikipedia.org/wiki/Chernoff_bound Неравенство Чернова]
 [[Категория: Теория сложности]]

@@ Строка 2: / Строка 2: @@
 {{Определение
 |definition =
-<tex>\mathrm{BPP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых для которых существует такая [[Вероятностные вычисления. Вероятностная машина Тьюринга |ВМТ]] <tex>p</tex>, что для любого <tex>x</tex>:
+<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> для любой [[Вероятностные вычисления. Вероятностная машина Тьюринга |вероятностной ленты]].

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

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

@@ Строка 1: / Строка 1: @@
 ==Определения==
 {{Определение
 |definition=