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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (переименовал Класс ZPP в Сложностный класс ZPP: Новая версия статьи будет называться "Класс ZPP", при этом пока не хочется избавляться от э...)
Строка 1: Строка 1:
 +
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 +
|+
 +
|-align="center"
 +
|'''НЕТ ВОЙНЕ'''
 +
|-style="font-size: 16px;"
 +
|
 +
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 +
 +
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 +
 +
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 +
 +
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 +
 +
''Антивоенный комитет России''
 +
|-style="font-size: 16px;"
 +
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 +
|-style="font-size: 16px;"
 +
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 +
|}
 +
 
===Определения===
 
===Определения===
 
Классом <tex>ZPP</tex> называется множество языков, для которых существует [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]] такая, что математическое ожидание времени ее работы на входе длины <tex>n</tex> равно <tex>O(poly(n))</tex>.
 
Классом <tex>ZPP</tex> называется множество языков, для которых существует [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]] такая, что математическое ожидание времени ее работы на входе длины <tex>n</tex> равно <tex>O(poly(n))</tex>.

Версия 09:02, 1 сентября 2022

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Определения

Классом [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]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].

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

Замечание

В дальнейшем будем рассматривать то определение класса [math]ZPP[/math], которое более удобно.