Теорема о включении BPP в P/poly - История изменений

Diniska: /* Доказательство */

2010-06-17T12:16:07Z

‎Доказательство

192.168.0.2 в 10:55, 17 июня 2010

2010-06-17T10:55:49Z

192.168.0.2: /* Доказательство */

2010-06-17T08:06:59Z

‎Доказательство

Vadim: /* Формулировка */

2010-06-17T00:48:51Z

‎Формулировка

Vadim: /* Доказательство */

2010-06-17T00:48:30Z

‎Доказательство

192.168.0.2: /* Доказательство */

2010-04-22T20:04:24Z

‎Доказательство

192.168.0.2: /* Доказательство */

2010-04-22T20:00:40Z

‎Доказательство

192.168.0.2: /* Доказательство */

2010-04-22T19:53:52Z

‎Доказательство

Vadim: /* Формулировка */

2010-04-21T19:22:56Z

‎Формулировка

Vadim: Новая страница: «== Формулировка == $BPP \subset P/poly$ »

2010-04-21T19:20:19Z

Новая страница: «== Формулировка == <math>BPP \subset P/poly</math>»

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

== Формулировка ==

<math>BPP \subset P/poly</math>

← Предыдущая		Версия 12:16, 17 июня 2010
Строка 5:		Строка 5:
	== Доказательство ==		== Доказательство ==

−	Для доказательства данной теоремы воспользуемся сильным определением [[Сложностный_класс_BPP\|BPP]]. Возьмём случайную последовательность, как дополнительный вход, который будет решать для любого входа <tex> x </tex> c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из <tex> BPP </tex> и добьёмся вероятности ошибки <tex> \frac{1}{2^{n+1}}</tex>, где <tex> n = \|x\| </tex> (длина входа). Будем говорить, что <tex> r </tex> "плохо" для <tex> x </tex>, если ответ неверный. Пусть <tex> t </tex> общее количество возможных вероятностных лент для <tex> r </tex>. Для каждого <tex> x </tex> по крайне мере <tex> \frac{t}{2^{n+1}}</tex> "плохих" значений <tex> r</tex>. Cуммирую по всем <tex> x </tex>, мы получим, что по крайне мере <tex> \frac{t \cdot 2^{n}}{2^{n+1}}</tex> "плохих" <tex> r </tex> для <tex> x </tex>. С другой стороны, хотя бы <tex> t/2 </tex> значений <tex> r </tex> не "плохи" для любого <tex> x </tex>. Получается, что точно найдётся такое <tex> r </tex>, при котором будет получается всегда верный результат. Полученное <tex> r </tex> будет являться подсказкой для заданной длины <tex> n </tex>. Таким образом мы получили, что язык из <tex> BPP </tex> принадлежит <tex>P/poly</tex>.	+	Для доказательства данной теоремы воспользуемся сильным определением [[Сложностный_класс_BPP\|BPP]]. Возьмём случайную последовательность, как дополнительный вход r, который будет решать для любого входа <tex> x </tex> c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из <tex> BPP </tex> и добьёмся вероятности ошибки <tex> \frac{1}{2^{n+1}}</tex>, где <tex> n = \|x\| </tex> (длина входа). Будем говорить, что <tex> r </tex> "плохо" для <tex> x </tex>, если ответ неверный. Пусть <tex> t </tex> общее количество возможных вероятностных лент для <tex> r </tex>. Для каждого <tex> x </tex> по крайне мере <tex> \frac{t}{2^{n+1}}</tex> "плохих" значений <tex> r</tex>. Cуммирую по всем <tex> x </tex>, мы получим, что по крайне мере <tex> \frac{t \cdot 2^{n}}{2^{n+1}}</tex> "плохих" <tex> r </tex> для <tex> x </tex>. С другой стороны, хотя бы <tex> t/2 </tex> значений <tex> r </tex> не "плохи" для любого <tex> x </tex>. Получается, что точно найдётся такое <tex> r </tex>, при котором будет получается всегда верный результат. Полученное <tex> r </tex> будет являться подсказкой для заданной длины <tex> n </tex>. Таким образом мы получили, что язык из <tex> BPP </tex> принадлежит <tex>P/poly</tex>.

← Предыдущая		Версия 10:55, 17 июня 2010
Строка 5:		Строка 5:
	== Доказательство ==		== Доказательство ==

−	Для доказательства данной теоремы воспользуемся сильным определением [[Сложностный_класс_BPP\|BPP]]. Возьмём случайную последовательность, как дополнительный вход, который будет решать для любого входа <tex> x </tex> c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из <tex> BPP </tex> и добьёмся вероятности ошибки <tex> \frac{1}{2^{n+1}}</tex>, где <tex> n = \|x\| </tex> (длина входа). Будем говорить, что <tex> r </tex> "плохо" для <tex> x </tex>, если ответ неверный. Пусть <tex> t </tex> общее количество ~~выборов~~ для <tex> r </tex>. Для каждого <tex> x </tex> по крайне мере <tex> \frac{t}{2^{n+1}}</tex> "плохих" значений <tex> r</tex>. Cуммирую по всем <tex> x </tex>, мы получим, что по крайне мере <tex> \frac{t*2^{n}}{2^{n+1}}</tex> "плохих" <tex> r </tex> для <tex> x </tex>. С другой стороны, хотя бы <tex> t/2 </tex> значений <tex> r </tex> не "плохи" для любого <tex> x </tex>. Получается, что точно найдётся такое <tex> r </tex>, при котором будет получается всегда верный результат. Полученное <tex> r </tex> будет являться подсказкой для заданной длины <tex> n </tex>. Таким образом мы получили, что язык из <tex> BPP </tex> принадлежит <tex>P/poly</tex>.	+	Для доказательства данной теоремы воспользуемся сильным определением [[Сложностный_класс_BPP\|BPP]]. Возьмём случайную последовательность, как дополнительный вход, который будет решать для любого входа <tex> x </tex> c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из <tex> BPP </tex> и добьёмся вероятности ошибки <tex> \frac{1}{2^{n+1}}</tex>, где <tex> n = \|x\| </tex> (длина входа). Будем говорить, что <tex> r </tex> "плохо" для <tex> x </tex>, если ответ неверный. Пусть <tex> t </tex> общее количество возможных вероятностных лент для <tex> r </tex>. Для каждого <tex> x </tex> по крайне мере <tex> \frac{t}{2^{n+1}}</tex> "плохих" значений <tex> r</tex>. Cуммирую по всем <tex> x </tex>, мы получим, что по крайне мере <tex> \frac{t \cdot 2^{n}}{2^{n+1}}</tex> "плохих" <tex> r </tex> для <tex> x </tex>. С другой стороны, хотя бы <tex> t/2 </tex> значений <tex> r </tex> не "плохи" для любого <tex> x </tex>. Получается, что точно найдётся такое <tex> r </tex>, при котором будет получается всегда верный результат. Полученное <tex> r </tex> будет являться подсказкой для заданной длины <tex> n </tex>. Таким образом мы получили, что язык из <tex> BPP </tex> принадлежит <tex>P/poly</tex>.

← Предыдущая		Версия 08:06, 17 июня 2010
Строка 5:		Строка 5:
	== Доказательство ==		== Доказательство ==

−	Для доказательства данной теоремы воспользуемся сильным определением [[Сложностный_класс_BPP\|BPP]]. Возьмём случайную последовательность, как дополнительный вход, который будет решать для любого входа <tex> x </tex> c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из <tex> BPP </tex> и добьёмся вероятности ошибки <tex> \frac{1}{2^{n+1}}</tex>, где <tex> n = \|x\| </tex> (длина входа). Будем говорить, что <tex> r </tex> "плохо" для <tex> x </tex>, если ответ неверный. Пусть <tex> t </tex> общее количество выборов для <tex> r </tex>. Для каждого <tex> x </tex> по крайне мере <tex> \frac{t}{2^{n+1}}</tex> "плохих" значений <tex> r</tex>. Cуммирую по всем <tex> x </tex>, мы получим, что по крайне мере <tex> \frac{t*2^{n}}{2^{n+1}}</tex> "плохих" <tex> r </tex> для <tex> x </tex>. С другой стороны, хотя бы <tex> t/2 </tex> значений <tex> r </tex> не "плохи" для любого <tex> x </tex>. Получается, что точно найдётся такое <tex> r </tex>, при котором будет получается всегда верный результат. Таким образом мы получили, что язык из <tex> BPP </tex> принадлежит <tex>P/poly</tex>.	+	Для доказательства данной теоремы воспользуемся сильным определением [[Сложностный_класс_BPP\|BPP]]. Возьмём случайную последовательность, как дополнительный вход, который будет решать для любого входа <tex> x </tex> c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из <tex> BPP </tex> и добьёмся вероятности ошибки <tex> \frac{1}{2^{n+1}}</tex>, где <tex> n = \|x\| </tex> (длина входа). Будем говорить, что <tex> r </tex> "плохо" для <tex> x </tex>, если ответ неверный. Пусть <tex> t </tex> общее количество выборов для <tex> r </tex>. Для каждого <tex> x </tex> по крайне мере <tex> \frac{t}{2^{n+1}}</tex> "плохих" значений <tex> r</tex>. Cуммирую по всем <tex> x </tex>, мы получим, что по крайне мере <tex> \frac{t*2^{n}}{2^{n+1}}</tex> "плохих" <tex> r </tex> для <tex> x </tex>. С другой стороны, хотя бы <tex> t/2 </tex> значений <tex> r </tex> не "плохи" для любого <tex> x </tex>. Получается, что точно найдётся такое <tex> r </tex>, при котором будет получается всегда верный результат. Полученное <tex> r </tex> будет являться подсказкой для заданной длины <tex> n </tex>. Таким образом мы получили, что язык из <tex> BPP </tex> принадлежит <tex>P/poly</tex>.

@@ Строка 1: / Строка 1: @@
 == Формулировка ==
-<math>BPP \subset P/poly</math>
+<tex>BPP \subset P/poly</tex>
 == Доказательство ==
 Для доказательства данной теоремы воспользуемся сильным определением [[Сложностный_класс_BPP|BPP]]. Возьмём случайную последовательность, как дополнительный вход, который будет решать для любого входа <tex> x </tex> c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из <tex> BPP </tex> и добьёмся вероятности ошибки <tex> \frac{1}{2^{n+1}}</tex>, где <tex> n = |x| </tex> (длина входа). Будем говорить, что <tex> r </tex> "плохо" для <tex> x </tex>, если ответ неверный. Пусть <tex> t </tex> общее количество выборов для <tex> r </tex>. Для каждого <tex> x </tex> по крайне мере <tex> \frac{t}{2^{n+1}}</tex> "плохих" значений <tex> r</tex>. Cуммирую по всем <tex> x </tex>, мы получим, что по крайне мере <tex> \frac{t*2^{n}}{2^{n+1}}</tex> "плохих" <tex> r </tex> для <tex> x </tex>. С другой стороны, хотя бы <tex> t/2 </tex> значений <tex> r </tex> не "плохи" для любого <tex> x </tex>. Получается, что точно найдётся такое <tex> r </tex>, при котором будет получается всегда верный результат. Таким образом мы получили, что язык из <tex> BPP </tex> принадлежит <tex>P/poly</tex>.

← Предыдущая		Версия 00:48, 17 июня 2010
Строка 5:		Строка 5:
	== Доказательство ==		== Доказательство ==

−	Для доказательства данной теоремы воспользуемся сильным определением ~~<math>~~ BPP ~~</math>~~. Возьмём случайную последовательность, как дополнительный вход, который будет решать для любого входа <~~math~~> x </~~math~~> c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из <~~math~~> BPP </~~math~~> и добьёмся вероятности ошибки <~~math~~> \frac{1}{2^{n+1}}</~~math~~>, где <~~math~~> n = \|x\| </~~math~~> (длина входа). Будем говорить, что <~~math~~> r </~~math~~> "плохо" для <~~math~~> x </~~math~~>, если ответ неверный. Пусть <~~math~~> t </~~math~~> общее количество выборов для <~~math~~> r </~~math~~>. Для каждого <~~math~~> x </~~math~~> по крайне мере <~~math~~> \frac{t}{2^{n+1}}</~~math~~> "плохих" значений <~~math~~> r</~~math~~>. Cуммирую по всем <~~math~~> x </~~math~~>, мы получим, что по крайне мере <~~math~~> \frac{t*2^{n}}{2^{n+1}}</~~math~~> "плохих" <~~math~~> r </~~math~~> для <~~math~~> x </~~math~~>. С другой стороны, хотя бы <~~math~~> t/2 </~~math~~> значений <~~math~~> r </~~math~~> не "плохи" для любого <~~math~~> x </~~math~~>. Получается, что точно найдётся такое <~~math~~> r </~~math~~>, при котором будет получается всегда верный результат. Таким образом мы получили, что язык из <~~math~~> BPP </~~math~~> принадлежит <~~math~~>P/poly</~~math~~>.	+	Для доказательства данной теоремы воспользуемся сильным определением [[Сложностный_класс_BPP\|BPP]]. Возьмём случайную последовательность, как дополнительный вход, который будет решать для любого входа <tex> x </tex> c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из <tex> BPP </tex> и добьёмся вероятности ошибки <tex> \frac{1}{2^{n+1}}</tex>, где <tex> n = \|x\| </tex> (длина входа). Будем говорить, что <tex> r </tex> "плохо" для <tex> x </tex>, если ответ неверный. Пусть <tex> t </tex> общее количество выборов для <tex> r </tex>. Для каждого <tex> x </tex> по крайне мере <tex> \frac{t}{2^{n+1}}</tex> "плохих" значений <tex> r</tex>. Cуммирую по всем <tex> x </tex>, мы получим, что по крайне мере <tex> \frac{t*2^{n}}{2^{n+1}}</tex> "плохих" <tex> r </tex> для <tex> x </tex>. С другой стороны, хотя бы <tex> t/2 </tex> значений <tex> r </tex> не "плохи" для любого <tex> x </tex>. Получается, что точно найдётся такое <tex> r </tex>, при котором будет получается всегда верный результат. Таким образом мы получили, что язык из <tex> BPP </tex> принадлежит <tex>P/poly</tex>.

← Предыдущая		Версия 20:04, 22 апреля 2010
Строка 5:		Строка 5:
	== Доказательство ==		== Доказательство ==

−	Для доказательства данной теоремы воспользуемся сильным определением <math> BPP </math>. Возьмём случайную последовательность, как дополнительный вход, который будет решать для любого входа <math> x </math> c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из <math> BPP </math> и добьёмся вероятности ошибки <math> \frac{1}{2^{n+1}}</math>, где <math> n = \|x\| </math> (длина входа). Будем говорить, что <math> r </math> "плохо" для <math> x </math>, если ответ неверный. Пусть <math> t </math> общее количество выборов для <math> r </math>. Для каждого <math> x </math> по крайне мере <math> \frac{t}{2^{n+1}}</math> "плохих" значений <math> r</math>. Cуммирую по всем <math> x </math>, мы получим, что по крайне мере <math> \frac{t*2^{n}}{2^{n+1}}</math> "плохих" <math> r </math> для <math> x </math>. С другой стороны, хотя бы <math> t/2 </math> значений <math> r </math> не "плохи" для любого <math> x </math>	+	Для доказательства данной теоремы воспользуемся сильным определением <math> BPP </math>. Возьмём случайную последовательность, как дополнительный вход, который будет решать для любого входа <math> x </math> c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из <math> BPP </math> и добьёмся вероятности ошибки <math> \frac{1}{2^{n+1}}</math>, где <math> n = \|x\| </math> (длина входа). Будем говорить, что <math> r </math> "плохо" для <math> x </math>, если ответ неверный. Пусть <math> t </math> общее количество выборов для <math> r </math>. Для каждого <math> x </math> по крайне мере <math> \frac{t}{2^{n+1}}</math> "плохих" значений <math> r</math>. Cуммирую по всем <math> x </math>, мы получим, что по крайне мере <math> \frac{t*2^{n}}{2^{n+1}}</math> "плохих" <math> r </math> для <math> x </math>. С другой стороны, хотя бы <math> t/2 </math> значений <math> r </math> не "плохи" для любого <math> x </math>. Получается, что точно найдётся такое <math> r </math>, при котором будет получается всегда верный результат. Таким образом мы получили, что язык из <math> BPP </math> принадлежит <math>P/poly</math>.

← Предыдущая		Версия 20:00, 22 апреля 2010
Строка 5:		Строка 5:
	== Доказательство ==		== Доказательство ==

−	Для доказательства данной теоремы воспользуемся сильным определением <math> BPP </math>. Возьмём случайную последовательность, как дополнительный вход, который будет решать для любого входа <math> x </math> c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из <math> BPP </math> и добьёмся вероятности ошибки <math> \frac{1}{2^{n+1}}</math>, где <math> n = \|x\| </math> (длина входа). Будем говорить, что <math> r </math> "плохо" для <math> x </math>, если ответ неверный. Пусть <math> t </math> общее количество выборов для <math> r </math>. Для каждого <math> x </math> по крайне мере <math> \frac{t}{2^{n+1}}</math> "плохих" значений <math> r</math>.	+	Для доказательства данной теоремы воспользуемся сильным определением <math> BPP </math>. Возьмём случайную последовательность, как дополнительный вход, который будет решать для любого входа <math> x </math> c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из <math> BPP </math> и добьёмся вероятности ошибки <math> \frac{1}{2^{n+1}}</math>, где <math> n = \|x\| </math> (длина входа). Будем говорить, что <math> r </math> "плохо" для <math> x </math>, если ответ неверный. Пусть <math> t </math> общее количество выборов для <math> r </math>. Для каждого <math> x </math> по крайне мере <math> \frac{t}{2^{n+1}}</math> "плохих" значений <math> r</math>. Cуммирую по всем <math> x </math>, мы получим, что по крайне мере <math> \frac{t*2^{n}}{2^{n+1}}</math> "плохих" <math> r </math> для <math> x </math>. С другой стороны, хотя бы <math> t/2 </math> значений <math> r </math> не "плохи" для любого <math> x </math>

← Предыдущая		Версия 19:53, 22 апреля 2010
Строка 5:		Строка 5:
	== Доказательство ==		== Доказательство ==

−	Для доказательства данной теоремы воспользуемся сильным определением <math> BPP </math>.	+	Для доказательства данной теоремы воспользуемся сильным определением <math> BPP </math>. Возьмём случайную последовательность, как дополнительный вход, который будет решать для любого входа <math> x </math> c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из <math> BPP </math> и добьёмся вероятности ошибки <math> \frac{1}{2^{n+1}}</math>, где <math> n = \|x\| </math> (длина входа). Будем говорить, что <math> r </math> "плохо" для <math> x </math>, если ответ неверный. Пусть <math> t </math> общее количество выборов для <math> r </math>. Для каждого <math> x </math> по крайне мере <math> \frac{t}{2^{n+1}}</math> "плохих" значений <math> r</math>.

← Предыдущая		Версия 19:22, 21 апреля 2010
Строка 2:		Строка 2:

	<math>BPP \subset P/poly</math>		<math>BPP \subset P/poly</math>
		+
		+	== Доказательство ==
		+
		+	Для доказательства данной теоремы воспользуемся сильным определением <math> BPP </math>.

Теорема о включении BPP в P/poly - История изменений

Diniska: /* Доказательство */

192.168.0.2 в 10:55, 17 июня 2010

192.168.0.2: /* Доказательство */

Vadim: /* Формулировка */

Vadim: /* Доказательство */

192.168.0.2: /* Доказательство */

192.168.0.2: /* Доказательство */

192.168.0.2: /* Доказательство */

Vadim: /* Формулировка */

Vadim: Новая страница: «== Формулировка == BPP \subset P/poly»

Vadim: Новая страница: «== Формулировка == $BPP \subset P/poly$ »