Вероятностная машина Тьюринга и сложность вычислений

Введение

Математическая модель вычислений

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

Описание

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

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

В результате ошибки, возникающей из-за использования вероятностных подбрасываний монеты, понятие принятия строки вероятностной машиной Тьюринга может быть определено различными способами. Одно из таких понятий, включающее несколько важных классов сложности, допускает вероятность ошибки 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?) считается еще более вероятным. С другой стороны, вычислительная мощность, которую случайность предоставляет интерактивным системам доказательств, а также простые алгоритмы, которые она позволяет создать для сложных задач, таких как проверка простоты за полиномиальное время и проверка связности графа в логарифмическом пространстве, позволяют предположить, что случайность действительно может увеличивать вычислительную мощность.

As a result of the error introduced by utilizing probabilistic coin tosses, the notion of acceptance of a string by a probabilistic Turing machine can be defined in different ways. One such notion that includes several important complexity classes is allowing for an error probability of 1/3. For instance, the complexity class BPP is defined as the class of languages recognized by a probabilistic Turing machine in polynomial time with an error probability of 1/3. Another class defined using this notion of acceptance is BPL, which is the same as BPP but places the additional restriction that languages must be solvable in logarithmic space. Complexity classes arising from other definitions of acceptance include RP, co RP, and ZPP. If the machine is restricted to logarithmic space instead of polynomial time, the analogous RL, co RL, and ZPL complexity classes are obtained. By enforcing both restrictions, RLP, co RLP, BPLP, and ZPLP are yielded. Probabilistic computation is also critical for the definition of most classes of interactive proof systems, in which the verifier machine depends on randomness to avoid being predicted and tricked by the all powerful prover machine. For example, the class IP equals PSPACE, but if randomness is removed from the verifier, we are left with only NP, which is not known but widely believed to be a considerably smaller class. One of the central questions of complexity theory is whether randomness adds power; that is, is there a problem that can be solved in polynomial time by a probabilistic Turing machine but not a deterministic Turing machine? Or can deterministic Turing machines efficiently simulate all probabilistic Turing machines with at most a polynomial slowdown? It is known that P ⊆ BPP, since a deterministic Turing machine is just a special case of a probabilistic Turing machine. However, it is uncertain whether (but widely suspected that) BPP ⊆ P, implying that BPP = P. The same question for log space instead of polynomial time (does L = BPLP?) is even more widely believed to be true. On the other hand, the power randomness gives to interactive proof systems, as well as the simple algorithms it creates for difficult problems such as polynomial time primality testing and log space graph connectedness testing, suggests that randomness may add power.