Класс 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 замкнут относительно взятия дополнения.
|
<imagemap>: неверное или отсутствующее изображение |
В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена.
Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 13 мая 2011 года. |
Напишите отзыв о статье "Класс ZPP"
Отрывок, характеризующий Класс ZPP
И она, как всегда говоря о Пьере, стала рассказывать анекдоты о его рассеянности, анекдоты, которые даже выдумывали на него.– Вы знаете, я поверил ему нашу тайну, – сказал князь Андрей. – Я знаю его с детства. Это золотое сердце. Я вас прошу, Натали, – сказал он вдруг серьезно; – я уеду, Бог знает, что может случиться. Вы можете разлю… Ну, знаю, что я не должен говорить об этом. Одно, – чтобы ни случилось с вами, когда меня не будет…
– Что ж случится?…
– Какое бы горе ни было, – продолжал князь Андрей, – я вас прошу, m lle Sophie, что бы ни случилось, обратитесь к нему одному за советом и помощью. Это самый рассеянный и смешной человек, но самое золотое сердце.
Ни отец и мать, ни Соня, ни сам князь Андрей не могли предвидеть того, как подействует на Наташу расставанье с ее женихом. Красная и взволнованная, с сухими глазами, она ходила этот день по дому, занимаясь самыми ничтожными делами, как будто не понимая того, что ожидает ее. Она не плакала и в ту минуту, как он, прощаясь, последний раз поцеловал ее руку. – Не уезжайте! – только проговорила она ему таким голосом, который заставил его задуматься о том, не нужно ли ему действительно остаться и который он долго помнил после этого. Когда он уехал, она тоже не плакала; но несколько дней она не плача сидела в своей комнате, не интересовалась ничем и только говорила иногда: – Ах, зачем он уехал!
Но через две недели после его отъезда, она так же неожиданно для окружающих ее, очнулась от своей нравственной болезни, стала такая же как прежде, но только с измененной нравственной физиогномией, как дети с другим лицом встают с постели после продолжительной болезни.
Здоровье и характер князя Николая Андреича Болконского, в этот последний год после отъезда сына, очень ослабели. Он сделался еще более раздражителен, чем прежде, и все вспышки его беспричинного гнева большей частью обрушивались на княжне Марье. Он как будто старательно изыскивал все больные места ее, чтобы как можно жесточе нравственно мучить ее. У княжны Марьи были две страсти и потому две радости: племянник Николушка и религия, и обе были любимыми темами нападений и насмешек князя. О чем бы ни заговорили, он сводил разговор на суеверия старых девок или на баловство и порчу детей. – «Тебе хочется его (Николеньку) сделать такой же старой девкой, как ты сама; напрасно: князю Андрею нужно сына, а не девку», говорил он. Или, обращаясь к mademoiselle Bourime, он спрашивал ее при княжне Марье, как ей нравятся наши попы и образа, и шутил…
Он беспрестанно больно оскорблял княжну Марью, но дочь даже не делала усилий над собой, чтобы прощать его. Разве мог он быть виноват перед нею, и разве мог отец ее, который, она всё таки знала это, любил ее, быть несправедливым? Да и что такое справедливость? Княжна никогда не думала об этом гордом слове: «справедливость». Все сложные законы человечества сосредоточивались для нее в одном простом и ясном законе – в законе любви и самоотвержения, преподанном нам Тем, Который с любовью страдал за человечество, когда сам он – Бог. Что ей было за дело до справедливости или несправедливости других людей? Ей надо было самой страдать и любить, и это она делала.