Сложностный класс ZPP — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
(Доказательство)
Строка 16: Строка 16:
 
==Доказательство==
 
==Доказательство==
  
<tex>1)ZPP \supset ZPP^{'}</tex>
+
*<tex>ZPP \supset ZPP^{'}</tex>
  
 
Пусть язык <tex>L \in ZPP^{'}</tex>, тогда для него существует [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]] <tex>m_1</tex>. Построим [[Вероятностная машина Тьюринга|вероятностную машину Тьюринга]] <tex>m_2</tex>, которая на входе <tex>x</tex> работает следущим образом:
 
Пусть язык <tex>L \in ZPP^{'}</tex>, тогда для него существует [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]] <tex>m_1</tex>. Построим [[Вероятностная машина Тьюринга|вероятностную машину Тьюринга]] <tex>m_2</tex>, которая на входе <tex>x</tex> работает следущим образом:
  
*Запускает <tex>m_1(x)</tex>.
+
1) Запускает <tex>m_1(x)</tex>.
  
*Если <tex>m_1(x)=0</tex> или <tex>m_1(x)=1</tex>, то <tex>m_2</tex> возвращает <tex>0</tex> или <tex>1</tex> соответственно. Если же <tex>m_1(x)=?</tex>, то начнем сначала.
+
2) Если <tex>m_1(x)=0</tex> или <tex>m_1(x)=1</tex>, то <tex>m_2</tex> возвращает <tex>0</tex> или <tex>1</tex> соответственно. Если же <tex>m_1(x)=?</tex>, то перейдем к пункту 1.
  
<tex>E(T(m_2(x)))= \sum_{i}^{ \infty } poly(x)*p^i*i = poly(x) * \sum_{i}^{ \infty } \frac{i}{2^i}</tex>
+
<tex>E(T(m_2(x)))= \sum_{i}^{ \infty } poly(x) \cdot p^i \cdot i = poly(x) \cdot \sum_{i}^{ \infty } \frac{i}{2^i}</tex>
  
 
<tex>\sum_{i}^{ \infty } \frac{i}{2^i}</tex> сходится.
 
<tex>\sum_{i}^{ \infty } \frac{i}{2^i}</tex> сходится.
  
Таким образом <tex>E(T(m_2(x)))=O(ploly(|x|))</tex>, значит <tex>ZPP \supset ZPP^{'}</tex>.
+
Таким образом <tex>E(T(m_2(x)))=O(poly(|x|))</tex>, значит <tex>ZPP \supset ZPP^{'}</tex>.
  
<tex>2)ZPP \subset ZPP^{'}</tex>
+
*<tex>ZPP \subset ZPP^{'}</tex>
  
 
Пусть язык <tex>L \in ZPP</tex>, тогда для него существует [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]] <tex>m_1</tex> такая, что <tex>E(T(m_1(x))) \le p(|x|)</tex>, где <tex>p \in poly</tex>.
 
Пусть язык <tex>L \in ZPP</tex>, тогда для него существует [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]] <tex>m_1</tex> такая, что <tex>E(T(m_1(x))) \le p(|x|)</tex>, где <tex>p \in poly</tex>.
  
Сделаем машину <tex>m_2</tex>, которая будет запускать <tex>m_1</tex> на <tex>2*p(|x|)</tex> шагов, если <tex>m_1</tex> не завершила свою работу, то <tex>m_2</tex> выдаст 'не знаю', в противном случаи вернет результат работы <tex>m_1</tex>.
+
Сделаем машину <tex>m_2</tex>, которая будет запускать <tex>m_1</tex> на <tex>2 \cdot p(|x|)</tex> шагов, если <tex>m_1</tex> не завершила свою работу, то <tex>m_2</tex> выдаст 'не знаю', в противном случаи вернет результат работы <tex>m_1</tex>.
  
 
Пусть <tex>p(m_1(x) = ?) > \frac{1}{2}</tex>, тогда <tex>E(T(m_1(x))) > p(|x|)</tex> &mdash; противоречие.
 
Пусть <tex>p(m_1(x) = ?) > \frac{1}{2}</tex>, тогда <tex>E(T(m_1(x))) > p(|x|)</tex> &mdash; противоречие.

Версия 15:56, 15 апреля 2010

Определения

Классом [math]ZPP[/math] называется множество языков, для которых существует вероятностная машина Тьюринга такая, что математическое ожидание времени ее работы на входе длинны [math]n[/math] равно [math]O(poly(n))[/math].

[math]ZPP = \{ L | \exists m : L(m)=L, E(T(m(x))) = O(poly(|x|)) \}[/math]

Альтернативное определение

Классом [math]ZPP^{'}[/math] называется множество языков, для которых существует вероятностная машина Тьюринга [math]m[/math] такая, что время ее работы на входе длинны [math]n[/math] не превосходит [math]poly(n)[/math]. У [math]m[/math] есть три конечных состояния: 'да', 'нет', 'не знаю' и [math]p(m(x) = [/math]'не знаю'[math]) \le \frac{1}{2}[/math]

[math]ZPP^{'} = \{ L | \exists m : L(m)=L, T(m(x)) \le poly(|x|) p(m(x) = ?) \le \frac{1}{2} \}[/math].

Утверждение

[math]ZPP = ZPP^{'}[/math]

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

  • [math]ZPP \supset ZPP^{'}[/math]

Пусть язык [math]L \in ZPP^{'}[/math], тогда для него существует вероятностная машина Тьюринга [math]m_1[/math]. Построим вероятностную машину Тьюринга [math]m_2[/math], которая на входе [math]x[/math] работает следущим образом:

1) Запускает [math]m_1(x)[/math].

2) Если [math]m_1(x)=0[/math] или [math]m_1(x)=1[/math], то [math]m_2[/math] возвращает [math]0[/math] или [math]1[/math] соответственно. Если же [math]m_1(x)=?[/math], то перейдем к пункту 1.

[math]E(T(m_2(x)))= \sum_{i}^{ \infty } poly(x) \cdot p^i \cdot i = poly(x) \cdot \sum_{i}^{ \infty } \frac{i}{2^i}[/math]

[math]\sum_{i}^{ \infty } \frac{i}{2^i}[/math] сходится.

Таким образом [math]E(T(m_2(x)))=O(poly(|x|))[/math], значит [math]ZPP \supset ZPP^{'}[/math].

  • [math]ZPP \subset ZPP^{'}[/math]

Пусть язык [math]L \in ZPP[/math], тогда для него существует вероятностная машина Тьюринга [math]m_1[/math] такая, что [math]E(T(m_1(x))) \le p(|x|)[/math], где [math]p \in poly[/math].

Сделаем машину [math]m_2[/math], которая будет запускать [math]m_1[/math] на [math]2 \cdot p(|x|)[/math] шагов, если [math]m_1[/math] не завершила свою работу, то [math]m_2[/math] выдаст 'не знаю', в противном случаи вернет результат работы [math]m_1[/math].

Пусть [math]p(m_1(x) = ?) \gt \frac{1}{2}[/math], тогда [math]E(T(m_1(x))) \gt p(|x|)[/math] — противоречие.

Значит, [math]p(m_1(x) = ?) \le \frac{1}{2}[/math], следовательно [math]L \in ZPP^{'}[/math].

Таким образом [math]ZPP \subset ZPP^{'}[/math].

Утверждение доказано.