Материал из Викиконспекты
| Определение: |
[math]\mathrm{ZPP}[/math] (от zero-error probabilistic polynomial) — множество языков [math]L[/math], для которых [math]\exists p \forall x[/math]:
- [math]\operatorname{P}(p(x) \ne [x \in L]) = 0[/math];
- [math]\operatorname{E}[\operatorname{T}(p, x)] = poly(|x|)[/math].
|
[math]\mathrm{ZPP}[/math] — сложностный класс, такой что программы, удовлетворяющие его ограничениям, не могут делать ошибок, но работают за полиномиальное время только в среднем случае.
Напомним, что математическое ожидание является усреднением по вероятностным лентам, а не по входу [math]x[/math].
Для данного класса существует и другое определение. Ниже мы покажем, что оба определения эквивалентны.
| Определение: |
[math]\mathrm{ZPP}_1[/math] — множество языков [math]L[/math], для которых [math]\exists p \forall x[/math]:
- [math]p(x) \in \{0, 1, ?\}[/math];
- [math]p(x) \ne \enskip? \Rightarrow p(x) = [x \in L][/math];
- [math]\operatorname{P}(p(x) = \enskip?) \le 1/2[/math];
- [math]\forall r \operatorname{T}(p, x) \le poly(|x|).[/math]
|
| Утверждение: |
[math]\mathrm{ZPP} = \mathrm{ZPP}_1[/math]. |
| [math]\triangleright[/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]. |
| [math]\triangleleft[/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 = \mathrm{RP} \cap \mathrm{coRP}[/math]. Тогда из [math]\mathrm{ZPP} = \mathrm{ZPP}_1[/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] |
