Класс ZPP

Поделись знанием:
(перенаправлено с «ZPP»)
Перейти к: навигация, поиск

В теории вычислительной сложности, ZPP (zero-error probabilistic polynomial time — безошибочный вероятностный полиномиальный) это такой класс задач, для которых существует вероятностная машина Тьюринга, удовлетворяющая нескольким свойствам:

  • Она всегда правильно отвечает «Да» либо «Нет».
  • Время работы такой машины неограниченно, но математическое ожидание времени работы полиномиальное.

Существует альтернативный набор свойств:

  • Машина Тьюринга всегда работает за полиномиальное время.
  • Она отвечает «Да», «Нет» или «Не знаю».
  • Ответ может быть либо правильным, либо «Не знаю».
  • Если правильный ответ «Да», машина Тьюринга отвечает «Да» с вероятностью не меньше ½.
  • Если правильный ответ «Нет», машина Тьюринга отвечает «Нет» с вероятностью не меньше ½.

Оба набора свойств эквивалентны.

Машину Тьюринга, удовлетворяющую этим свойствам, называют иногда машиной Тьюринга типа Лас-Вегас.



Определение через пересечение

Класс ZPP в точности эквивалентен пересечению классов RP и Co-RP. Часто именно это принимается за определение ZPP. Чтобы продемонстрировать это, заметим, что любая задача принадлежащая одновременно RP и co-RP имеет алгоритм типа Лас-Вегас:

  • Допустим есть язык L распознаваемый RP алгоритмом A и (возможно совершенно другим) co-RP алгоритмом B.
  • Запустим A на входной последовательности. Если он ответит «Да», то окончательный ответ должен быть «Да». В противном случае запустим B с тем же входом. Если он ответит «Нет», то окончательный ответ должен быть «Нет». Если не выполнено ни одно из предыдущих, повторим данный шаг.

Заметим, что лишь один из алгоритмов A или B может дать неправильный ответ, и вероятность этого события равняется на каждом шаге 50 %. Т.о. вероятность достигнуть k-го шага уменьшается экспоненциально относительно k. Это показывает, что математическое ожидание времени работы полиномиальное. Из сказанного следует, что пересечение RP и co-RP содержится в ZPP.

Покажем, что ZPP содержится в пересечении RP и co-RP. Пусть имеется машина Тьюринга типа Лас-Вегас C, которая решает задачу. Можно построить следующий RP алгоритм:

  • Запустим C в течение по крайней мере удвоенного ожидаемого времени работы. Если получен ответ — возвращаем его. Если до момента останова никакого ответа не получено, говорим «Нет».

Вероятность того, что будет получен ответ до момента останова, равняется ½ (из неравенства Маркова). Это в свою очередь означает, что вероятность ответить «Нет», когда на самом деле ответ «Да», за счет останова, равна ½, что удовлетворяет определению RP. Для доказательства включения ZPP в co-RP можно либо воспользоваться тем же рассуждением, либо заметить, что ZPP замкнут относительно взятия дополнения.


К:Википедия:Статьи без источников (тип: не указан)

Напишите отзыв о статье "Класс ZPP"

Отрывок, характеризующий Класс ZPP

И она, как всегда говоря о Пьере, стала рассказывать анекдоты о его рассеянности, анекдоты, которые даже выдумывали на него.
– Вы знаете, я поверил ему нашу тайну, – сказал князь Андрей. – Я знаю его с детства. Это золотое сердце. Я вас прошу, Натали, – сказал он вдруг серьезно; – я уеду, Бог знает, что может случиться. Вы можете разлю… Ну, знаю, что я не должен говорить об этом. Одно, – чтобы ни случилось с вами, когда меня не будет…
– Что ж случится?…
– Какое бы горе ни было, – продолжал князь Андрей, – я вас прошу, m lle Sophie, что бы ни случилось, обратитесь к нему одному за советом и помощью. Это самый рассеянный и смешной человек, но самое золотое сердце.
Ни отец и мать, ни Соня, ни сам князь Андрей не могли предвидеть того, как подействует на Наташу расставанье с ее женихом. Красная и взволнованная, с сухими глазами, она ходила этот день по дому, занимаясь самыми ничтожными делами, как будто не понимая того, что ожидает ее. Она не плакала и в ту минуту, как он, прощаясь, последний раз поцеловал ее руку. – Не уезжайте! – только проговорила она ему таким голосом, который заставил его задуматься о том, не нужно ли ему действительно остаться и который он долго помнил после этого. Когда он уехал, она тоже не плакала; но несколько дней она не плача сидела в своей комнате, не интересовалась ничем и только говорила иногда: – Ах, зачем он уехал!
Но через две недели после его отъезда, она так же неожиданно для окружающих ее, очнулась от своей нравственной болезни, стала такая же как прежде, но только с измененной нравственной физиогномией, как дети с другим лицом встают с постели после продолжительной болезни.


Здоровье и характер князя Николая Андреича Болконского, в этот последний год после отъезда сына, очень ослабели. Он сделался еще более раздражителен, чем прежде, и все вспышки его беспричинного гнева большей частью обрушивались на княжне Марье. Он как будто старательно изыскивал все больные места ее, чтобы как можно жесточе нравственно мучить ее. У княжны Марьи были две страсти и потому две радости: племянник Николушка и религия, и обе были любимыми темами нападений и насмешек князя. О чем бы ни заговорили, он сводил разговор на суеверия старых девок или на баловство и порчу детей. – «Тебе хочется его (Николеньку) сделать такой же старой девкой, как ты сама; напрасно: князю Андрею нужно сына, а не девку», говорил он. Или, обращаясь к mademoiselle Bourime, он спрашивал ее при княжне Марье, как ей нравятся наши попы и образа, и шутил…
Он беспрестанно больно оскорблял княжну Марью, но дочь даже не делала усилий над собой, чтобы прощать его. Разве мог он быть виноват перед нею, и разве мог отец ее, который, она всё таки знала это, любил ее, быть несправедливым? Да и что такое справедливость? Княжна никогда не думала об этом гордом слове: «справедливость». Все сложные законы человечества сосредоточивались для нее в одном простом и ясном законе – в законе любви и самоотвержения, преподанном нам Тем, Который с любовью страдал за человечество, когда сам он – Бог. Что ей было за дело до справедливости или несправедливости других людей? Ей надо было самой страдать и любить, и это она делала.