Класс ZPP — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Здесь будет новая статья)
Строка 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]

Версия 22:40, 4 июня 2012

Эта статья находится в разработке!


Определение:
[math]\mathrm{ZPP}[/math] (от zero-error probabilistic polynomial) — множество языков [math]L[/math], для которых [math]\exists p \forall x[/math]:
  1. [math]\operatorname{P}(p(x) \ne [x \in L]) = 0[/math];
  2. [math]\operatorname{E}[\operatorname{T}(p, x)] = poly(|x|)[/math].

[math]\mathrm{ZPP}[/math] — сложностный класс, такой что программы, удовлетворяющие его ограничениям, не могут делать ошибок, но работают за полиномиальное время только в среднем случае.

Напомним, что математическое ожидание является усреднением по вероятностным лентам, а не по входу [math]x[/math].


Теорема:
[math]\mathrm{P} \subset \mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}[/math].
Доказательство:
[math]\triangleright[/math]

Утверждение [math]\mathrm{P} \subset \mathrm{ZPP}[/math] является очевидным, так как программы, удовлетворяющие ограничениям [math]\mathrm{P}[/math], также удовлетворяют ограничениям класса [math]\mathrm{ZPP}[/math].

Покажем, что [math]\mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}[/math]. Для этого определим вспомогательный класс [math]\mathrm{ZPP}_1[/math].

Определение:
[math]\mathrm{ZPP}_1[/math] — множество языков [math]L[/math], для которых [math]\exists p \forall x[/math]:
  1. [math]p(x) \in \{0, 1, ?\}[/math];
  2. [math]p(x) \ne \enskip? \Rightarrow p(x) = [x \in L][/math];
  3. [math]\operatorname{P}(p(x) = \enskip?) \le 1/2[/math];
  4. [math]\forall r \operatorname{T}(p, x) \le poly(|x|).[/math]

1. Сначала докажем, что [math]\mathrm{ZPP} = \mathrm{ZPP}_1[/math].

1) [math]\mathrm{ZPP} \subset \mathrm{ZPP}_1[/math].

Пусть [math]X[/math] — случайная величина, равная времени работы программы [math]p[/math] для [math]\mathrm{ZPP}[/math], [math]X \gt 0[/math]. Запишем неравенство Маркова:

[math]\operatorname{P}(X \gt k \operatorname{E}[X]) \le 1/k[/math].

Подставим [math]k = 2[/math]. Тогда, если запустить программу [math]p[/math] для [math]\mathrm{ZPP}[/math] с ограничением по времени [math]2E[X][/math], она не успеет завершиться с вероятностью, не превышающей [math]1/2[/math]. Опишем программу [math]q[/math] для [math]\mathrm{ZPP}_1[/math]. Она будет возвращать [math]?[/math], если [math]p[/math] не успеет завершиться, а иначе — результат работы программы [math]p[/math]. Заметим, что [math]q[/math] работает полиномиальное время, так как [math]E[X][/math] ограничено некоторым полиномом по определению класса [math]\mathrm{ZPP}[/math].

2) [math]\mathrm{ZPP_1} \subset \mathrm{ZPP}[/math]. Будем запускать программу [math]p[/math] для [math]\mathrm{ZPP_1}[/math], пока не получим ответ, отличный от [math]?[/math]. Математическое ожидание количества запусков [math]p[/math] не превышает [math]\sum\limits_{k = 0}^\infty \frac{k}{2^k} = 2[/math]. Значит, новая программа будет в среднем работать за полиномиальное время, что и требуется для класса [math]\mathrm{ZPP}[/math].

2. Теперь покажем, что [math]\mathrm{ZPP}_1 = \mathrm{RP} \cap \mathrm{coRP}[/math].

1) [math]\mathrm{ZPP}_1 \subset \mathrm{RP}[/math]. Достаточно вместо [math]?[/math] возвращать [math]0[/math].

2) [math]\mathrm{ZPP}_1 \subset\mathrm{coRP}[/math]. Достаточно вместо [math]?[/math] возвращать [math]1[/math].

3) [math]\mathrm{ZPP}_1 \supset \mathrm{RP} \cap \mathrm{coRP}[/math]. Пусть программа [math]p_1[/math] удовлетворяет ограничениям [math]\mathrm{RP}[/math] и ошибается на словах из языка [math]L[/math] с вероятностью не более [math]1/2[/math], а программа [math]p_2[/math] удовлетворяет ограничениям [math]\mathrm{coRP}[/math] и ошибается на словах не из языка [math]L[/math] с аналогичной вероятностью. Построим программу [math]q[/math] для [math]\mathrm{ZPP}_1[/math]:

 [math]q[/math](x)
   if [math]p_2[/math](x) = 0
     return 0
   if [math]p_1[/math](x) = 1
     return 1
   return ?
Вероятность вывести [math]?[/math] есть [math]\operatorname{P}(p_2(x) = 1, p_1(x) = 0) \le 1/2[/math].
[math]\triangleleft[/math]

Литература