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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:43:48Z

rollbackEdits.php mass rollback

185.220.100.241 в 03:15, 1 сентября 2022

2022-09-01T03:15:42Z

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

2012-06-04T20:48:37Z

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

2012-06-04T20:36:57Z

Igor buzhinsky в 19:57, 4 июня 2012

2012-06-04T19:57:08Z

Igor buzhinsky в 19:40, 4 июня 2012

2012-06-04T19:40:38Z

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

2012-06-04T19:35:29Z

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

Igor buzhinsky: переименовал Класс ZPP в Сложностный класс ZPP: Новая версия статьи будет называться "Класс ZPP", при этом пока не хочется избавляться от э...

2012-06-04T19:26:53Z

переименовал Класс ZPP в Сложностный класс ZPP: Новая версия статьи будет называться "Класс ZPP", при этом пока не хочется избавляться от э...

Новая страница

#перенаправление [[Сложностный класс ZPP]]

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

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

@@ Строка 33: / Строка 33: @@
 . <tex>\mathrm{ZPP_1} \subset \mathrm{ZPP}</tex>.
 Будем запускать программу <tex>p</tex> для <tex>\mathrm{ZPP_1}</tex>, пока не получим ответ, отличный от <tex>?</tex>. Математическое ожидание количества запусков <tex>p</tex> не превышает <tex>\sum\limits_{k = 0}^\infty \frac{k}{2^k} = 2</tex>. Значит, новая программа будет в среднем работать за полиномиальное время, что и требуется для класса <tex>\mathrm{ZPP}</tex>.
 }}
 == Литература ==
 * [http://www.cs.princeton.edu/theory/complexity/ Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach]

@@ Строка 10: / Строка 10: @@
-{{Теорема
+Для данного класса существует и другое определение. Ниже мы покажем, что оба определения эквивалентны.
 {{Определение
 |definition =
@@ Строка 25: / Строка 19: @@
 # <tex>\forall r \operatorname{T}(p, x) \le poly(|x|).</tex>
 }}
-) <tex>\mathrm{ZPP} \subset \mathrm{ZPP}_1</tex>.
+{{Утверждение
 Пусть <tex>X</tex> — случайная величина, равная времени работы программы <tex>p</tex> для <tex>\mathrm{ZPP}</tex>, <tex>X > 0</tex>. Запишем [http://ru.wikipedia.org/wiki/Неравенство_Маркова неравенство Маркова]:
@@ Строка 35: / Строка 31: @@
 Подставим <tex>k = 2</tex>. Тогда, если запустить программу <tex>p</tex> для <tex>\mathrm{ZPP}</tex> с ограничением по времени <tex>2E[X]</tex>, она не успеет завершиться с вероятностью, не превышающей <tex>1/2</tex>. Опишем программу <tex>q</tex> для <tex>\mathrm{ZPP}_1</tex>. Она будет возвращать <tex>?</tex>, если <tex>p</tex> не успеет завершиться, а иначе — результат работы программы <tex>p</tex>. Заметим, что <tex>q</tex> работает полиномиальное время, так как <tex>E[X]</tex> ограничено некоторым полиномом по определению класса <tex>\mathrm{ZPP}</tex>.
-) <tex>\mathrm{ZPP_1} \subset \mathrm{ZPP}</tex>.
+. <tex>\mathrm{ZPP_1} \subset \mathrm{ZPP}</tex>.
 Будем запускать программу <tex>p</tex> для <tex>\mathrm{ZPP_1}</tex>, пока не получим ответ, отличный от <tex>?</tex>. Математическое ожидание количества запусков <tex>p</tex> не превышает <tex>\sum\limits_{k = 0}^\infty \frac{k}{2^k} = 2</tex>. Значит, новая программа будет в среднем работать за полиномиальное время, что и требуется для класса <tex>\mathrm{ZPP}</tex>.
-. Теперь покажем, что <tex>\mathrm{ZPP}_1 = \mathrm{RP} \cap \mathrm{coRP}</tex>.
+Докажем, что <tex>\mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>.
 ) <tex>\mathrm{ZPP}_1 \subset \mathrm{RP}</tex>. Достаточно вместо <tex>?</tex> возвращать <tex>0</tex>.

← Предыдущая		Версия 19:57, 4 июня 2012
Строка 1:		Строка 1:
−	~~{{В разработке}}~~
−
	{{Определение		{{Определение
	\|definition =		\|definition =

← Предыдущая		Версия 19:40, 4 июня 2012
Строка 1:		Строка 1:
	{{В разработке}}		{{В разработке}}

−	~~Здесь~~ будет ~~статья~~.	+	{{Определение
		+	\|definition =
		+	<tex>\mathrm{ZPP}</tex> (от ''zero-error probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:
		+	# <tex>\operatorname{P}(p(x) \ne [x \in L]) = 0</tex>;<br>
		+	# <tex>\operatorname{E}[\operatorname{T}(p, x)] = poly(\|x\|)</tex>.<br>
		+	}}
		+	<tex>\mathrm{ZPP}</tex> — сложностный класс, такой что программы, удовлетворяющие его ограничениям, не могут делать ошибок, но работают за полиномиальное время только в среднем случае.
		+
		+	Напомним, что математическое ожидание является усреднением по вероятностным лентам, а не по входу <tex>x</tex>.
		+
		+
		+	{{Теорема
		+	\|statement = <tex>\mathrm{P} \subset \mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>.
		+	\|proof =
		+	Утверждение <tex>\mathrm{P} \subset \mathrm{ZPP}</tex> является очевидным, так как программы, удовлетворяющие ограничениям <tex>\mathrm{P}</tex>, также удовлетворяют ограничениям класса <tex>\mathrm{ZPP}</tex>.
		+
		+	Покажем, что <tex>\mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>.
		+	Для этого определим вспомогательный класс <tex>\mathrm{ZPP}_1</tex>.
		+	{{Определение
		+	\|definition =
		+	<tex>\mathrm{ZPP}_1</tex> — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:
		+	# <tex>p(x) \in \{0, 1, ?\}</tex>;
		+	# <tex>p(x) \ne \enskip? \Rightarrow p(x) = [x \in L]</tex>;
		+	# <tex>\operatorname{P}(p(x) = \enskip?) \le 1/2</tex>;
		+	# <tex>\forall r \operatorname{T}(p, x) \le poly(\|x\|).</tex>
		+	}}
		+	1. Сначала докажем, что <tex>\mathrm{ZPP} = \mathrm{ZPP}_1</tex>.
		+
		+	1) <tex>\mathrm{ZPP} \subset \mathrm{ZPP}_1</tex>.
		+
		+	Пусть <tex>X</tex> — случайная величина, равная времени работы программы <tex>p</tex> для <tex>\mathrm{ZPP}</tex>, <tex>X > 0</tex>. Запишем [http://ru.wikipedia.org/wiki/Неравенство_Маркова неравенство Маркова]:
		+
		+	<tex>\operatorname{P}(X > k \operatorname{E}[X]) \le 1/k</tex>.
		+
		+	Подставим <tex>k = 2</tex>. Тогда, если запустить программу <tex>p</tex> для <tex>\mathrm{ZPP}</tex> с ограничением по времени <tex>2E[X]</tex>, она не успеет завершиться с вероятностью, не превышающей <tex>1/2</tex>. Опишем программу <tex>q</tex> для <tex>\mathrm{ZPP}_1</tex>. Она будет возвращать <tex>?</tex>, если <tex>p</tex> не успеет завершиться, а иначе — результат работы программы <tex>p</tex>. Заметим, что <tex>q</tex> работает полиномиальное время, так как <tex>E[X]</tex> ограничено некоторым полиномом по определению класса <tex>\mathrm{ZPP}</tex>.
		+
		+	2) <tex>\mathrm{ZPP_1} \subset \mathrm{ZPP}</tex>.
		+	Будем запускать программу <tex>p</tex> для <tex>\mathrm{ZPP_1}</tex>, пока не получим ответ, отличный от <tex>?</tex>. Математическое ожидание количества запусков <tex>p</tex> не превышает <tex>\sum\limits_{k = 0}^\infty \frac{k}{2^k} = 2</tex>. Значит, новая программа будет в среднем работать за полиномиальное время, что и требуется для класса <tex>\mathrm{ZPP}</tex>.
		+
		+	2. Теперь покажем, что <tex>\mathrm{ZPP}_1 = \mathrm{RP} \cap \mathrm{coRP}</tex>.
		+
		+	1) <tex>\mathrm{ZPP}_1 \subset \mathrm{RP}</tex>. Достаточно вместо <tex>?</tex> возвращать <tex>0</tex>.
		+
		+	2) <tex>\mathrm{ZPP}_1 \subset\mathrm{coRP}</tex>. Достаточно вместо <tex>?</tex> возвращать <tex>1</tex>.
		+
		+	3) <tex>\mathrm{ZPP}_1 \supset \mathrm{RP} \cap \mathrm{coRP}</tex>.
		+	Пусть программа <tex>p_1</tex> удовлетворяет ограничениям <tex>\mathrm{RP}</tex> и ошибается на словах из языка <tex>L</tex> с вероятностью не более <tex>1/2</tex>, а программа <tex>p_2</tex> удовлетворяет ограничениям <tex>\mathrm{coRP}</tex> и ошибается на словах не из языка <tex>L</tex> с аналогичной вероятностью. Построим программу <tex>q</tex> для <tex>\mathrm{ZPP}_1</tex>:
		+	<tex>q</tex>(x)
		+	'''if''' <tex>p_2</tex>(x) = 0
		+	'''return''' 0
		+	'''if''' <tex>p_1</tex>(x) = 1
		+	'''return''' 1
		+	'''return''' ?
		+
		+	Вероятность вывести <tex>?</tex> есть <tex>\operatorname{P}(p_2(x) = 1, p_1(x) = 0) \le 1/2</tex>.
		+	}}
		+
		+	== Литература ==
		+	* [http://www.cs.princeton.edu/theory/complexity/ Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach]

← Предыдущая		Версия 19:35, 4 июня 2012
Строка 1:		Строка 1:
−	~~#перенаправление [[Сложностный класс ZPP]]~~	+	{{В разработке}}
		+
		+	Здесь будет статья.