Научная Сеть >> М.Н. Вялый "Сложность вычислительных задач"

Наука >> Математика >> Математическое образование | Популярные статьи

Next: 8.2. Определение класса IP Up: 8. Класс IP Previous: 8. Класс IP Contents: Содержание

8.1. Дополнительные возможности: подбрасывание монетки и класс BPP

Для начала нужно понять, что изменится в определении алгоритма, если разрешить использование генератора случайности. Результат работы Исполнителя, использующего подбрасывания монетки, перестает быть однозначно определенным. Как тогда понимать утверждение "алгоритм (вероятностный) решает задачу"?

Естественно полагать, что вероятностный алгоритм решает задачу, если велика вероятность правильного ответа. Конечно, эта вероятность зависит от свойств генератора случайности. Мы будем считать, что генератор случайности производит последовательность независимых случайных битов (0 или 1 с равными вероятностями). Простейшая реальная модель такого генератора - подбрасывание монетки.

Если известна верхняя оценка времени работы алгоритма, то его можно преобразовать к следующему стандартному виду: сделаем достаточное количество подбрасываний монетки и запомним их результаты, составив таблицу случайных битов. После этого начнем действовать по алгоритму, заменяя подбрасывание монетки обращением к таблице случайных чисел, составленной на первом шаге. Время работы такой версии алгоритма имеет ту же (с точностью до мультипликативного множителя) верхнюю оценку. А вероятность получения ответа для алгоритма в таком формате подсчитывается просто: это отношение количества тех таблиц случайных чисел, при использовании которых получается данный ответ , к общему количеству таблиц, равному , где - количество случайных битов.

Это замечание позволяет дать определение класса $\ensuremath{\mathrm {BPP}}$ - задач, решаемых вероятностными алгоритмами за полиномиальное время, - аналогично определению 5 класса $\ensuremath{\mathrm {NP}}$ .

Определение 7. Функция принадлежит классу $\ensuremath{\mathrm {BPP}}$ , если существуют такие полином $q(\cdot)$ и функция $R(\cdot,\cdot)\in\P$ , что доля слов длины $q(\vert x\vert)$ , для которых выполнено , больше .

Если в этом определении заменить число на любое фиксированное число, большее , класс $\ensuremath{\mathrm {BPP}}$ не изменится. Есть простой способ добиться вероятности, сколь угодно близкой к 1. Возьмем несколько одинаковых машин, запустим их все, а окончательным результатом будем считать мнение большинства. Если вероятность правильного ответа для каждого экземпляра машины равна , то вероятность неправильного ответа после голосования машин

$\begin{displaymath} \begin{split} \sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{k}c^... ...lfloor n/2\rfloor} \frac{1}{1-(1-c)/c}=O(\lambda^n) \end{split}\end{displaymath}$ (16)

для подходящего $\lambda$ ( $2\sqrt{c(1-c)}<\lambda<1$ ). Таким образом, голосование экспоненциально быстро уменьшает вероятность неправильного ответа.

Next: 8.2. Определение класса IP Up: 8. Класс IP Previous: 8. Класс IP Contents: Содержание

МЦНМО

Написать комментарий