Теорема Лаутемана — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Доказательство)
м (Доказательство)
Строка 6: Строка 6:
 
Из того, что класс <tex>\mathrm{BPP}</tex> замкнут относительно дополнения и <tex>\mathrm{co}\Sigma_2 = \Pi_2</tex> следует, что достаточно доказать включение <tex>\mathrm{BPP} \subset \Sigma_2</tex>.
 
Из того, что класс <tex>\mathrm{BPP}</tex> замкнут относительно дополнения и <tex>\mathrm{co}\Sigma_2 = \Pi_2</tex> следует, что достаточно доказать включение <tex>\mathrm{BPP} \subset \Sigma_2</tex>.
  
<tex>\mathrm{BPP}</tex> можно определить, как множество таких языков <tex>L</tex>, что <tex>x \in L \Leftrightarrow \exists</tex> «много» вероятностных лент <tex>y: R(x,y)</tex>. <tex>\Sigma_2</tex> определяется, как множество <tex>\{ L \mid x \in L \Leftrightarrow \exists y \forall z R(x, y, z)\}</tex>. Таким образом, необходимо уметь записывать <tex>\exists</tex> «много» с помощью кванторов <tex>\exists\forall</tex>.
+
<tex>\mathrm{BPP}</tex> можно определить как множество таких языков <tex>L</tex>, что <tex>x \in L \Leftrightarrow \exists</tex> «много» вероятностных лент <tex>y: R(x,y)</tex>. <tex>\Sigma_2</tex> определяется как множество <tex>\{ L \mid x \in L \Leftrightarrow \exists y \forall z R(x, y, z)\}</tex>. Таким образом, необходимо уметь записывать <tex>\exists</tex> «много» с помощью кванторов <tex>\exists\forall</tex>.
  
Рассмотрим язык <tex>G</tex> всех слов длины <tex>k</tex> над алфавитом <tex>\{0, 1\}</tex>, для некоторого <tex>k</tex>, значение которого будет получено позже. Определим операцию <tex>\oplus</tex> над славами из этого языка, как побитовое исключающее или.
+
Рассмотрим язык <tex>G</tex> всех слов длины <tex>k</tex> над алфавитом <tex>\{0, 1\}</tex> для некоторого <tex>k</tex>, значение которого будет получено позже. Определим операцию <tex>\oplus</tex> над словами из этого языка как побитовое исключающее или.
  
Назовем <tex>X</tex>, содержащееся в <tex>G</tex> большим, если существует набор <tex>g_1, g_2, \dots g_k</tex> такой, что <tex>\bigcup_{i=1}^{k} g_i \oplus X = G</tex>.
+
Назовем <tex>X</tex>, содержащееся в <tex>G</tex>, большим, если существует набор <tex>g_1, g_2, \dots g_k</tex> такой, что <tex>\bigcup_{i=1}^{k} g_i \oplus X = G</tex>.
  
Если <tex>k|X| < |G|</tex>, то <tex>X</tex> точное не является большим. Найдем достаточное условие, при котором <tex>X</tex> большой.
+
Если <tex>k|X| < |G|</tex>, то <tex>X</tex> точно не является большим. Найдем достаточное условие, при котором <tex>X</tex> большой.
  
 
Воспользуемся утверждением, что если вероятность <tex>P(x \in A) > 0</tex>, то существует <tex>x</tex> из <tex>A</tex>. Для этого  
 
Воспользуемся утверждением, что если вероятность <tex>P(x \in A) > 0</tex>, то существует <tex>x</tex> из <tex>A</tex>. Для этого  
Строка 18: Строка 18:
  
 
Для некотрого <tex>y \in G</tex>:
 
Для некотрого <tex>y \in G</tex>:
* <tex>P(y \in g_i \oplus X) = P(y \oplus g_i \in X) = \frac{|X|}{|G|}</tex>,
+
* <tex>P(y \in g_i \oplus X) = P(y \oplus g_i \in X) = \frac{|X|}{|G|}</tex>;
* <tex>P(y \not \in g_i \oplus X) = 1 - \frac{|X|}{|G|}</tex>
+
* <tex>P(y \not \in g_i \oplus X) = 1 - \frac{|X|}{|G|}</tex>;
* <tex>P(\bigwedge_{i=1}^{k} y \not \in g_i \oplus X) = \left(1 - \frac{|X|}{|G|}\right)^k</tex>
+
* <tex>P(\bigwedge_{i=1}^{k} y \not \in g_i \oplus X) = \left(1 - \frac{|X|}{|G|}\right)^k</tex>;
* <tex>P(\exists y \in G \bigwedge_{i=1}^{k} y \not \in g_i \oplus X) = |G|\left(1 - \frac{|X|}{|G|}\right)^k</tex>
+
* <tex>P(\exists y \in G \bigwedge_{i=1}^{k} y \not \in g_i \oplus X) = |G|\left(1 - \frac{|X|}{|G|}\right)^k</tex>.
  
 
Если <tex>|G|\left(1 - \frac{|X|}{|G|}\right)^k < 1</tex>, то существует набор <tex>\{g_i\}</tex>, что для любого <tex>y</tex> <tex>\bigwedge_{i=1}^{k} y \not \in g_i \oplus X</tex>, а из этого следует, что <tex>X</tex> большой.  
 
Если <tex>|G|\left(1 - \frac{|X|}{|G|}\right)^k < 1</tex>, то существует набор <tex>\{g_i\}</tex>, что для любого <tex>y</tex> <tex>\bigwedge_{i=1}^{k} y \not \in g_i \oplus X</tex>, а из этого следует, что <tex>X</tex> большой.  
  
Рассмотрим язык <tex>L \in \mathrm{BPP}</tex>. Не уменьшая общности, можем считать, <tex>p(|x|)</tex> шагов и вероятность ошибки не превосходит
+
Рассмотрим язык <tex>L \in \mathrm{BPP}</tex>. Не уменьшая общности, можем считать, что программа <tex>M</tex>, распознающая этот язык, завершается за <tex>p(|x|)</tex> шагов и вероятность ошибки не превосходит
 
<tex>\frac{1}{3p(|x|)}</tex>, это следует из того, что если запускать программу несколько раз, то время работы растет линейно, а вероятность ошибки
 
<tex>\frac{1}{3p(|x|)}</tex>, это следует из того, что если запускать программу несколько раз, то время работы растет линейно, а вероятность ошибки
экспоненциально уменьшается. Пусть его распознает машина <tex>M</tex>.
+
экспоненциально уменьшается.
  
 
Зафиксируем <tex>x</tex>. Возьмем <tex>k = p(|x|)</tex>. Рассмотрим множество начал длины <tex>k</tex> вероятностных лент <tex>X</tex>, на которых
 
Зафиксируем <tex>x</tex>. Возьмем <tex>k = p(|x|)</tex>. Рассмотрим множество начал длины <tex>k</tex> вероятностных лент <tex>X</tex>, на которых
Строка 33: Строка 33:
  
 
Из того, что вероятность ошибки не превосходит <tex>\frac1{3k}</tex>, следует:
 
Из того, что вероятность ошибки не превосходит <tex>\frac1{3k}</tex>, следует:
* <tex>x \in L \rightarrow \frac{|X|}{|G|} \geqslant 1 - \frac1{3k}</tex>
+
* <tex>x \in L \rightarrow \frac{|X|}{|G|} \geqslant 1 - \frac1{3k}</tex>;
* <tex>x \not \in L \rightarrow \frac{|X|}{|G|} \leqslant \frac1{3k}</tex>
+
* <tex>x \not \in L \rightarrow \frac{|X|}{|G|} \leqslant \frac1{3k}</tex>.
  
 
Если <tex>x \in L</tex>, то:
 
Если <tex>x \in L</tex>, то:

Версия 14:47, 12 апреля 2010

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

Утверждение теоремы Лаутемана (Sipser–Lautemann theorem или Sipser–Gács–Lautemann theorem) состоит в том, что класс BPP содержится в классах [math]\Sigma_2[/math] и [math]\Pi_2[/math] полиномиальной иерархии.

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

Из того, что класс [math]\mathrm{BPP}[/math] замкнут относительно дополнения и [math]\mathrm{co}\Sigma_2 = \Pi_2[/math] следует, что достаточно доказать включение [math]\mathrm{BPP} \subset \Sigma_2[/math].

[math]\mathrm{BPP}[/math] можно определить как множество таких языков [math]L[/math], что [math]x \in L \Leftrightarrow \exists[/math] «много» вероятностных лент [math]y: R(x,y)[/math]. [math]\Sigma_2[/math] определяется как множество [math]\{ L \mid x \in L \Leftrightarrow \exists y \forall z R(x, y, z)\}[/math]. Таким образом, необходимо уметь записывать [math]\exists[/math] «много» с помощью кванторов [math]\exists\forall[/math].

Рассмотрим язык [math]G[/math] всех слов длины [math]k[/math] над алфавитом [math]\{0, 1\}[/math] для некоторого [math]k[/math], значение которого будет получено позже. Определим операцию [math]\oplus[/math] над словами из этого языка как побитовое исключающее или.

Назовем [math]X[/math], содержащееся в [math]G[/math], большим, если существует набор [math]g_1, g_2, \dots g_k[/math] такой, что [math]\bigcup_{i=1}^{k} g_i \oplus X = G[/math].

Если [math]k|X| \lt |G|[/math], то [math]X[/math] точно не является большим. Найдем достаточное условие, при котором [math]X[/math] большой.

Воспользуемся утверждением, что если вероятность [math]P(x \in A) \gt 0[/math], то существует [math]x[/math] из [math]A[/math]. Для этого выберем случайно набор [math]\{g_i\}[/math].

Для некотрого [math]y \in G[/math]:

  • [math]P(y \in g_i \oplus X) = P(y \oplus g_i \in X) = \frac{|X|}{|G|}[/math];
  • [math]P(y \not \in g_i \oplus X) = 1 - \frac{|X|}{|G|}[/math];
  • [math]P(\bigwedge_{i=1}^{k} y \not \in g_i \oplus X) = \left(1 - \frac{|X|}{|G|}\right)^k[/math];
  • [math]P(\exists y \in G \bigwedge_{i=1}^{k} y \not \in g_i \oplus X) = |G|\left(1 - \frac{|X|}{|G|}\right)^k[/math].

Если [math]|G|\left(1 - \frac{|X|}{|G|}\right)^k \lt 1[/math], то существует набор [math]\{g_i\}[/math], что для любого [math]y[/math] [math]\bigwedge_{i=1}^{k} y \not \in g_i \oplus X[/math], а из этого следует, что [math]X[/math] большой.

Рассмотрим язык [math]L \in \mathrm{BPP}[/math]. Не уменьшая общности, можем считать, что программа [math]M[/math], распознающая этот язык, завершается за [math]p(|x|)[/math] шагов и вероятность ошибки не превосходит [math]\frac{1}{3p(|x|)}[/math], это следует из того, что если запускать программу несколько раз, то время работы растет линейно, а вероятность ошибки экспоненциально уменьшается.

Зафиксируем [math]x[/math]. Возьмем [math]k = p(|x|)[/math]. Рассмотрим множество начал длины [math]k[/math] вероятностных лент [math]X[/math], на которых машина [math]M[/math] выдает единицу, то есть [math]X = \{y \in G \mid M(x,y) = 1\}[/math].

Из того, что вероятность ошибки не превосходит [math]\frac1{3k}[/math], следует:

  • [math]x \in L \rightarrow \frac{|X|}{|G|} \geqslant 1 - \frac1{3k}[/math];
  • [math]x \not \in L \rightarrow \frac{|X|}{|G|} \leqslant \frac1{3k}[/math].

Если [math]x \in L[/math], то:

  • [math]\frac{|X|}{|G|} \geqslant 1 - \frac1{3k}[/math];
  • [math]1 - \frac{|X|}{|G|} \leqslant \frac1{3k}[/math];
  • [math]|G|\left(1 - \frac{|X|}{|G|}\right)^k \leqslant |G| \frac1{3k}^k = \frac2{3k}^k \lt 1[/math], что влечет за собой то, что [math]X[/math] большой.

Если [math]x \not \in[/math], то [math]\frac{|X|}{|G|} \leqslant \frac1{3k} \lt \frac1k[/math], а значит [math]X[/math] не является большим.

Таким образом, [math]x \in L \Leftrightarrow \exists k, g_1, g_2, \dots, g_k \forall y \bigvee_{i=1}^{m} y \in g_i \oplus X[/math], то есть [math]x \in L \Leftrightarrow \exists k, g_1, g_2, \dots, g_k \forall y \bigvee_{i=1}^{m} M(x, y \oplus g_i)[/math], а значит [math]L \in \Sigma_2[/math], [math]\mathrm{BPP} \subset \Sigma_2[/math] и [math]\mathrm{BPP} \subset \Sigma_2 \cap \Pi_2[/math], что и требовалось доказать.