Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений, страница 116

Таким образом, общая вероятность допускания неоднородной цепочки длиной 1 равна 2 '"'. Например, вероятность допускания 00101 — 1/64. Е3 Наш вывод состоит в том, что вероятность допускания любой цепочки данной рандомизированной МТ можно вычислить. Принадлежность цепочки языку зависит от того, как определено "членство" в языке рандомизированной МТ. В следующем разделе лают- ся два разных определения допускания, приводящие к различным классам языков.

11.4.4. Класс Я./э Язык А класса ЕР ("гавдос ро1упопна!" — случайные полиномиальные) допускается рандомизированной МТ Мв следующем смысле. 1. Если ж не принадлежитА, то вероятность того, что Мдопускает ж, равна О. 2. Если ж принадлежит Х, то вероятность того, что М допускает ж, не меньше 1/2. 3. Существует полипом р(п), для которого, если ж имеет длину и, то все вычисления М, независимо от содержимого случайной ленты, останавливаются после не более р(и) шагов.

Заметим, что определение класса 'ЕР использует два не связанных между собой свойства. Пункты 1 и 2 определяют рандомизированную МТ специального вида, которую иногда называют алгоритмом шипа Моцте-Карло. Таким образом, независимо от времени работы говорят, что рандомизированная МТ является машиной 'типа МонтеКарло", если она допускает нли с вероятностью О, нли с вероятностью больше 1/2, ничего не допуская с вероятностями между 0 и 1/2. В пункте 3 упоминается время работы, не зависящее от того, является ли МТ машиной типа Монте-Карло. Пример !1.14. Рассмотрим рандомизированную МТ из примера !1.13. Она удовлетворяет условию 3, поскольку время ее работы есть О(п) независимо от содержимого случайной ленты.

Однако она вообще не допускает никакого языка в смысле определения ТР. Причина в том, что, хотя однородные цепочки вроде 000 допускаются с вероятностью не меньше 1/2 и, таким образом, удовлетворяют условию 2, есть другие цепочки, вроде 001, допускаемые с вероятностью, не равной 0 и меньшей, чем 1/2 (цепочка 001 допускается с вероятностью 1/16). Е3 ГЛАВА 11. ДОПОЛНИТЕЛЬНЫЕ КЛАССЫ ПРОБЛЕМ 504 Пример 11.15. Неформально опишем рандомизированную МТ, которая одновременно полиномиальна по времени и является машиной типа Монте-Карло и, следовательно, допускает язык из РР. Ее вход интерпретируется как граф, и вопрос состоит в том, есть лн в этом графе треугольник, т.е.

три узла, попарно соединенных ребрами. Входы с тре- угольниками принадлежат языку, остальные — нет. Алгоритм Монте-Карло циклически выбирает ребро (х, у) и вершину х, отличную от х и у, случайным образом. Каждый выбор определяется просмотром нескольких новых случайных битов на случайной ленте. Для каждой тройки выбранных х, у и х МТ проверяет, содержит ли вход ребра (х, х) и (у, х), и, если так, объявляет, что вход содержит тре- угольник. Всего производится !г выборов ребра и вершины; МТ допускает, если любой из них дает треугольник, а если нет, не допускает. Если у графа нет треугольника, то ни один из к выборов не может показать его наличие, что соответствует условию 1 в определении 7сР— если вход не принадлежит языку, то вероятность его доцускания равна О. Предположим, что граф имеет и узлов и т ребер.

Если граф имеет хотя бы один треугольник, то вероятность того, что три его узла будут выбраны в одном эксперименте, (' 3'(' равна — — ~, т,е. три из т ребер находятся в треугольнике, и если любое из ннх ~т~,и-2~' выбрано, то вероятность того, что выбирается также и третий узел, равна 1/(и — 2). Эта вероятность мала, но эксперимент повторяется 4 раз. Поэтому вероятность того, что ни один из й экспериментов не даст треугольника, равна (11.4) т(и — 2) Для величины (1-х) при малых х часто используется приближение в виде е~, где е = 2.718...

— основание натуральных логарифмов. Если выбрать к так, что, например 1х = 1, то е~" будет заметно меньше 1!2 и 1 — е "* будет значительно больше 1/2 (около 0.63). Таким образом, можно выбрать й = т(и--2)/3, чтобы гарантировать, что вероятность допускания графа с треугольником, описанная формулой (!1.4), не меньше 1/2. Итак, описанный алгоритм является алгоритмом типа Монте-Карло. Нужно еше рассмотреть время работы МТ.

И и, и т не больше, чем длина входа, а значение А выбирается так, что оно не больше квадрата длины (пропорционально произведению и и т). В каждом эксперименте вход просматривается не более четырех раз (чтобы выбрать случайное ребро и узел, а затем проверить наличие еше двух ребер), поэтому время выполнения эксперимента линейно относительно длины входа. Таким образом, МТ останавливается, совершив переходов в количестве, не более чем кубическом относительно длины входа, т.е.МТ имеет полииомиальное время работы и, следовательно, удовлетворяет условию 3 определения принадлежности языка классу РР. 11.4.

КЛАССЫ ЯЗЫКОВ, ОСНОВАННЫЕ НА РАНДОМИЗАЦИИ 505 Приходим к выводу, что язык графов с треугольниками принадлежит классу ЯР. Отметим, что он также находится в 'Р, поскольку можно провести систематический полиномиапьный поиск всех треугольников.

Однако, как упоминалось в начале раздела ! !.4, найти примеры языков, которые оказались бы в аР- Р, в действительности трудно. 1:З 11.4.Б. Распознавание языков из /сР Предположим, что для распознавания языка Е у нас есть полиномиальная по времени машина Тьюринга М типа Монте-Карло. Нам дается цепочка и, и нужно узнать, принадлежит ли ш языку Ь. Запуская М на зг н используя бросание монеты или какое-либо другое устройство генерации случайных чисел для имитации создания случайных битов, по- лучаем следующее.

!. Если ш не принадлежит Х„то запуск наверняка не завершится допусканием зг. 2. Если в принадлежит Е, то существует не менее 50Ъ шансов, что и будет допущено. Однако если мы просто возьмем выход данного запуска в качестве определяющего, то и может оказаться отвергнутым, хотя должно быть допущено (ложный негативный исход, ложный пропуск), но мы никогда не допустим его, если не должны (ложный позитивный исход ложное допускание). Таким образом, следует отличать рандомизированную МТ от алгоритма, используемого для решения, находится ли зь в Ь.

В целом избежать ложных негативных исходов невозможно, хотя путем многократного повторения проверки вероятность ложного пропуска можно сделать как угодно малой. Например, если нужно сделать вероятность ложного пропуска не больше одной биллионной, можно запустить проверку тридцать раз. Если и принадлежит/., то шансы на то, что все тридцать проверок пропустят допускание, не больше 2 ', что меньше !О ~, или одной биллионной.

Вообще, если нам нужна вероятность ложного пропуска меньше, чем с > О, мы должны запусппь проверку !ояК!/с) раз. Это количество является константой, если с— константа, а один запуск рандомнзированной МТ М требует полиномиального времени, так как предполагается, что /, принадлежит Р,Р. Отсюда повторение проверки также требует полиномнального времени. Вывод из зтих рассуждений формулируется в следующей теореме.

Теорема 11.16. Если Ь принадлежит ЯР, то для любой как угодно малой константы с >О существует полиномиальный по времени рандомизированный алгоритм, решающий, принадлежит ли зг языку Ь, который не совершает ложных допусканий, а ложные пропуски делает с вероятностью не больше с. Е) 11.4.6. Класс ЯРР Второй класс языков, использующих рандомизацию, называется безошибочным вероятностным нолиномиачьным (сего-еггог, ргоЬаЬ!!!л!!с, ро!унот!а!), или ЯРР.

Класс основан на рандомизированной МТ, которая всегда останавливается и имеет ожидаемое 506 ГЛАВА 11. ДОПОЛНИТЕЛЬНЫЕ КЛАССЫ ПРОБЛЕМ время астапова, полиномиачьное относительно длины входа. Эта МТ допускает свой вход, если попадает в допускающее состояние (и при этом останавливается), и отвергает его, останавливаясь без допускания. Таким образом, определение класса гРР почти совпадает с определением класса Р, за исключением того, что гРР разрешает машине вести себя случайным образом, и ограничивается не время работы в худшем случае, а ожидаемое время работы.

МТ, которая всегда дает правильный ответ, но время работы которой зависит от значений некоторых случайных битов, иногда называется машиной Тьюринга типа ЛасВегас, или алгоритмом типа Лас-Вегас. Таким образом, класс ЯРР можно считать классом языков, допускаемых машинами Тьюринга типа Лас-Вегас с полиномиально ограниченным ожидаемым временем работы. Является ли дробь 1/2 особенной в определении 'КР7 Хотя в определении РР требовалось, чтобы вероятность допускания цепочки и из /. была не меньше 1/2, можно определить класс 7'Р с любой другой константой между 0 и 1 вместо 1/2.

Теорема 11.16 говори~, что мы могли бы, повторяя эксперимент, совершаемый М, подходящее число раз, сделать вероятность допускания сколь угодно большой, но строго меньшей 1. Кроме того, такая же техника уменьшения вероятности пропуска цепочки из /„использованная в разделе 11.4.5, позволит нам брать рандомизированную МТ с любой вероятностью допускания цепочки и из Е, превышающей О, и увеличивать эту вероятность до 1/2 путем повторения экспериментов неко- торое постоянное число раз. В определении РР мы продолжим требовать!/2 в качестве вероятности допускания, но осознавая, что для определения РР достаточно любой ненулевой вероятности. С другой стороны, изменение константы 1/2 изменит язык, определяемый конкретной рандомизированной МТ.