Класс PP

Класс PP

В теории сложности, PP является классом проблем, решаемых вероятностными машинами Тьюринга за полиномиальное время, с вероятностью ошибки менее 1/2. Аббревиатура PP обозначает «вероятностный полиномиальный по времени».

Определение

Язык L принадлежит PP тогда и только тогда, когда существует вероятностная машина Тьюринга M такая, что

  • M полиномиальна по времени
  • Для любого x из L, M возвращает 1 с вероятностью строго большей 1/2
  • Для любого x не из L, M возвращает 1 с вероятностью не большей 1/2

PP и BPP

BPP является подмножеством класса PP; его можно рассматривать как подмножество задач, для которых имеются эффективные вероятностные алгоритмы. Разница заключается в величине вероятности ошибки: в классе BPP, любой алгоритм должен дать правильный ответ с вероятностью больше, чем c (с > 1/2), например 2/3 или 777/1000. В этом случае, можно запустить алгоритм фиксированное количество раз, а затем выбрать ответ, имеющий большинство голосов, чтобы достигнуть определенной вероятности корректности меньше 1. Количество повторений увеличивается при приближении c к 1/2, но не зависит от n.

Замечание. c не может зависеть от входа. С другой стороны, алгоритм из PP может проделывать следующую последовательность действий:

  • Если правильный ответ «Да», алгоритм говорит «Да» с вероятностью 1/2+1/2n, где n — это длина входа.
  • Если правильный ответ «Нет», алгоритм говорит «Да» с вероятностью 1/2-1/2n.

Так как эти две возможности достаточно близки, в особенности для больших n, даже если машина Тьюринга будет запущена большое количество раз очень сложно понять, работаем ли мы с вариантом, где правильный ответ «Да» или «Нет». Попытка добиться фиксированного значения вероятности, используя большинство голосов, требует количество повторений, экспоненциальное по n. Грубо, это можно сравнить с задачей определения, какой стороной выпадет монетка с небольшим перевесом, подбрасывая ее большое количество раз.




Wikimedia Foundation. 2010.

Смотреть что такое "Класс PP" в других словарях:

  • класс — класс, а …   Русский орфографический словарь

  • класс — класс/ …   Морфемно-орфографический словарь

  • КЛАСС — (в логике и математике) 1) понятие, присущее всем элементам некоторой совокупности объектов; 2) совокупность выделенных по некоторому признаку объектов, мыслимая как целое. Понятие К. (множества) обычно относят к числу простейших, неопределяемых… …   Философская энциклопедия

  • Класс! — Класс! …   Википедия

  • КЛАСС — (лат. classis порядок.). 1) разряд однородных предметов. 2) собрание учеников для учебных занятий, а также помещение и самое время, назначенное для урока. 3) степень в государственной службе. Словарь иностранных слов, вошедших в состав русского… …   Словарь иностранных слов русского языка

  • класс — сущ., м., употр. часто Морфология: (нет) чего? класса, чему? классу, (вижу) что? класс, чем? классом, о чём? о классе; мн. что? классы, (нет) чего? классов, чему? классам, (вижу) что? классы, чем? классами, о чём? о классах 1. Классом называют… …   Толковый словарь Дмитриева

  • КЛАСС — КЛАСС, [ас] класса, м. [латин. classis]. 1. Социальная группа, часть общества, объединенная общностью интересов вследствие одинакового отношения к средствам производства и противостоящая другим социальным группам в силу противоположности… …   Толковый словарь Ушакова

  • КЛАСС! — КЛАСС! …   Википедия

  • КЛАСС — (class) Оксфордский словарь английского языка дает следующее определение класса: Разделение общества или порядок в обществе согласно статусу; разряд, категория общества . Но это определение класса столь же разъясняет, сколь и вносит путаницу.… …   Политология. Словарь.

  • класс — а; м. [от лат. classis разряд] 1. (чего) В научной терминологии: совокупность, группа предметов или явлений с общими признаками; разряд, категория. К. млекопитающих. К. земноводных. К. двудольных растений. Плавать на судах различных классов.… …   Энциклопедический словарь

  • класс — См. разряд …   Словарь синонимов

Книги

Другие книги по запросу «Класс PP» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»