Вероятностная машина Тьюринга

В теоретической информатике вероятностная машина Тьюринга — это недетерминированная машина Тьюринга , которая выбирает между доступными переходами в каждой точке в соответствии с некоторым распределением вероятностей . Как следствие, вероятностная машина Тьюринга может — в отличие от детерминированной машины Тьюринга — давать стохастические результаты; то есть на данном конечном автомате ввода и инструкции он может иметь разное время выполнения или может вообще не останавливаться; более того, он может принять ввод в одном исполнении и отклонить тот же ввод в другом исполнении.

В случае равных вероятностей переходов вероятностные машины Тьюринга можно определить как детерминированные машины Тьюринга, имеющие дополнительную инструкцию «записи», где значение записи равномерно распределено в алфавите машины Тьюринга (как правило, равная вероятность записи «1» или «0» на ленте). Другая распространенная формулировка — это просто детерминированная машина Тьюринга с добавленной лентой, полной случайных битов, называемой «случайной лентой».

Квантовый компьютер — еще одна модель вычислений, которая по своей сути является вероятностной.

Описание

Вероятностная машина Тьюринга — это тип недетерминированной машины Тьюринга , в которой каждый недетерминированный шаг представляет собой «подбрасывание монеты», то есть на каждом шаге есть два возможных следующих хода, и машина Тьюринга вероятностно выбирает, какой ход предпринять.

Формальное определение

Вероятностную машину Тьюринга можно формально определить как семикортеж $M=(Q,\Sigma ,\Gamma ,q_{0},A,\delta _{1},\delta _{2})$, где

• $Q$ это конечное множество состояний
• $\Sigma$ это входной алфавит
• $\Gamma$ представляет собой ленточный алфавит, включающий пустой символ #
• $q_{0}\in Q$ это начальное состояние
• $A\subseteq Q$ — множество принимающих (конечных) состояний
• $\delta _{1}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$ – первая вероятностная переходная функция. $L$ это движение на одну клетку влево на ленте машины Тьюринга и $R$ это движение на одну клетку вправо.
• $\delta _{2}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$ – вторая вероятностная переходная функция.

На каждом шаге машина Тьюринга вероятностно применяет либо функцию перехода $\delta _{1}$ или функция перехода $\delta _{2}$. Этот выбор делается независимо от всех предыдущих выборов. Таким образом, процесс выбора функции перехода на каждом этапе вычислений напоминает подбрасывание монеты.

Вероятностный выбор функции перехода на каждом шаге вносит ошибку в машину Тьюринга; то есть строки, которые машина Тьюринга должна принимать, в некоторых случаях могут быть отклонены, а строки, которые машина Тьюринга должна принимать, в некоторых случаях могут быть приняты. Чтобы обеспечить это, язык $L$ говорят, что распознается с вероятностью ошибки $\epsilon$ с помощью вероятностной машины Тьюринга $M$ если:

1. строка $w$ в $L$ подразумевает, что ${\text{Pr}}[M{\text{ accepts }}w]\geq 1-\epsilon$
2. строка $w$ не в $L$ подразумевает, что ${\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon$

Классы сложности

Нерешенная задача в информатике :

Является П = БПП ?

(еще нерешенные проблемы по информатике)

В результате ошибки, возникающей при использовании вероятностного подбрасывания монеты, понятие принятия строки вероятностной машиной Тьюринга может быть определено по-разному. Одним из таких понятий, включающим несколько важных классов сложности, является допущение вероятности ошибки 1/3. Например, класс сложности BPP определяется как класс языков, распознаваемых вероятностной машиной Тьюринга за полиномиальное время с вероятностью ошибки 1/3. Другой класс, определенный с использованием этого понятия принятия, — это BPL , который аналогичен BPP , но накладывает дополнительное ограничение, заключающееся в том, что языки должны быть разрешимы в логарифмическом пространстве .

Классы сложности, вытекающие из других определений приемки, включают RP , co-RP и ZPP . Если машина ограничена логарифмическим пространством вместо полиномиального времени, RL , co-RL и ZPL получаются аналогичные классы сложности . При применении обоих ограничений RLP , co-RLP , BPLP и ZPLP получаются .

Вероятностные вычисления также имеют решающее значение для определения большинства классов интерактивных систем доказательства , в которых проверяющая машина зависит от случайности, чтобы избежать предсказания и обмана всемогущей проверяющей машины. Например, класс IP равен PSPACE , но если убрать случайность из верификатора, у нас останется только NP , который неизвестен, но широко распространено мнение, что это значительно меньший класс.

Один из центральных вопросов теории сложности заключается в том, добавляет ли случайность силы; то есть существует ли проблема, которую можно решить за полиномиальное время с помощью вероятностной машины Тьюринга, но не детерминированной машины Тьюринга? Или могут ли детерминированные машины Тьюринга эффективно имитировать все вероятностные машины Тьюринга с не более чем полиномиальным замедлением? Известно, что P ⊆ BPP , поскольку детерминированная машина Тьюринга является лишь частным случаем вероятностной машины Тьюринга. Однако неясно, является ли BPP ⊆ P что это так) , а это означает, что BPP = P. (но широко распространено подозрение , Тот же вопрос для пространства журналов вместо полиномиального времени ( L = BPLP ?) еще более широко считается верным. С другой стороны, степень случайности, которую дает интерактивным системам доказательства, а также простые алгоритмы, которые она создает для сложных задач, таких как проверка простоты полиномиального времени и проверка связности графов в лог-пространстве, предполагают, что случайность может добавить мощности.

См. также

• Рандомизированный алгоритм

Ссылки

• Арора, Санджив ; Барак, Вооз (2016). Вычислительная сложность: современный подход . Издательство Кембриджского университета. стр. 123–142. ISBN  978-0-521-42426-4 .
• Сипсер, Майкл (2006). Введение в теорию вычислений (2-е изд.). США: Курс технологии Томсона. стр. 368–380. ISBN  978-0-534-95097-2 .

Внешние ссылки

• Веб-сайт NIST, посвященный вероятностным машинам Тьюринга