Изменения

Перейти к: навигация, поиск

Сложностный класс ZPP

2445 байт добавлено, 19:12, 4 сентября 2022
м
rollbackEdits.php mass rollback
===Определения===
Классом <tex>ZPP</tex> называется множество языков, для которых существует [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]] такая, что математическое ожидание времени ее работы на входе длинны длины <tex>n</tex> равно <tex>O(poly(n))</tex>.
<tex>ZPP = \{ L | \exists m : L(m)=L, E(T(m(x))) = O(poly(|x|)) \}</tex>
===Альтернативное определения===Введем в рассмотрение класс <tex>ZPP^{'}</tex>.
===Определение===Классом <tex>ZPP^{'}</tex> называется множество языков, для которых существует [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]] <tex>m</tex> такая, что временя время ее работы на входе длинны <tex>n</tex> не превосходит <tex>poly(n)</tex>. У <tex>m</tex> есть три конечных состояния: 'да', 'нет', 'не знаю' и <tex>p(m(x) = </tex>'не знаю'<tex>) \le \frac{1}{2}</tex>
<tex>ZPP^{'} = \{ L | \exists m : L(m)=L, T(m(x)) \le poly(|x|) p(m(x) = ?) \le \frac{1}{2} \}</tex>.
 
==Утверждение==
 
<tex>ZPP = ZPP^{'}</tex>
 
==Доказательство==
 
*<tex>ZPP \supset ZPP^{'}</tex>
 
Пусть язык <tex>L \in ZPP^{'}</tex>, тогда для него существует [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]] <tex>m_1</tex>. Построим [[Вероятностная машина Тьюринга|вероятностную машину Тьюринга]] <tex>m_2</tex>, которая на входе <tex>x</tex> работает следущим образом:
 
1) Запускает <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) \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>E(T(m_2(x)))=O(poly(|x|))</tex>, значит <tex>ZPP \supset 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>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) = ?) \le \frac{1}{2}</tex>, следовательно <tex>L \in ZPP^{'}</tex>.
 
Таким образом <tex>ZPP \subset ZPP^{'}</tex>.
 
Утверждение доказано.
 
===Замечание===
 
В дальнейшем будем рассматривать то определение класса <tex>ZPP</tex>, которое более удобно.
1632
правки

Навигация