ГЛАВА 11

Дополнительные классы проблем

Труднорешаемые проблемы не ограничиваются классом MP. Существует много других классов труднорешаемых проблем, по разным причинам представляющих интерес. Не­которые вопросы, связанные с этими классами, вроде V = MP, остаются нерешенными.

Вначале рассматривается класс, тесно связанный сРи MP, — класс дополнений язы­ков из MP, часто называемый «со-МР\ Если ‘Р = MP, то со-MP равен обоим, поскольку V замкнут относительно дополнения. Однако более вероятно, что со-MP отличается от обоих этих классов, и ни одна MP-полная проблема не принадлежит со-MP.

Далее изучается класс VS. Он образован проблемами, которые решаются на машинах Тьюринга с использованием объема ленты, полиномиального относительно длины входа. Этим машинам Тьюринга разрешается использовать экспоненциальное время, но огра­ниченную часть ленты. В отличие от ситуации с полиномиальным временем, здесь мож­но доказать, что при таком же ограничении пространства недетерминизм не увеличивает мощности МТ. Однако, несмотря на то, что VS очевидным образом включает MP, неиз­вестно, равны ли эти классы. Ожидается, что они не равны, и здесь мы опишем пробле­му, которая полна для VS и предположительно не принадлежит MP.

Затем обратимся к рандомизированным алгоритмам и двум классам языков, лежащим между V и MP. Один из этих классов обозначается TZV («random polynomial» languages — «случайные полиномиальные» языки). Эти языки имеют алгоритм, который работает по­линомиальное время, используя «бросание монеты» или (на практике) генератор случай­ных чисел. Алгоритм или подтверждает принадлежность входа языку, или отвечает «не знаю». Кроме того, если вход принадлежит языку, то существует некоторая вероятность больше 0, что алгоритм будет «докладывать об успехе», поэтому его повторное примене­ние будет с вероятностью, близкой к 1, подтверждать принадлежность.

Второй класс, называемый EVP (zero-error, probabilistic polynomial — безошибочные, вероятностные полиномиальные), также использует рандомизацию, но алгоритмы для языков этого класса отвечают: «да, вход принадлежит языку» или «нет, не принадлежит». Ожидаемое время работы алгоритма полиномиально. Однако возможно выполнение ал­горитма, требующее больше времени, чем полиномиальное.

Чтобы увязать приведенные понятия, рассмотрим важный вопрос проверки простоты. Многие современные системы шифрования основаны на следующих свойствах.

Способность быстро находить большие простые числа, чтобы защитить от посто­ронних воздействий канал сообщения между компьютерами.

Предположение о том, что разложение на целые сомножители требует экспоненциаль­ного времени, измеряемого в виде функции от длины п двоичной записи целого числа.

Будет показано, что проверка простоты чисел принадлежит как NT, та и со-NT, поэтому вряд ли удастся доказать NP-полноту этой проверки. Это плохо, так как доказательство NP-полноты является наиболее действенным доводом в пользу того, что проблема, ско­рее всего, требует экспоненциального времени. Будет показано также, что проверка про­стоты принадлежит классу 1ZT. Это и хорошо, и плохо. Хорошо, поскольку системы шифрования, использующие простые числа, применяют для их поиска алгоритм из клас­са TZT. Плохо, так как подтверждается предположение, что доказать NP-полноту провер­ки простоты так и не удастся.

11.1. Дополнения языков из JSfP

Класс языков Т замкнут относительно дополнения (см. упражнение 10.1.6). Это легко обосновать. Пусть L принадлежит V, а М— МТ для L. Для допускания L изменим М: введем новое допускающее состояние q и новые переходы в q из тех состояний, в кото­рых М останавливается, не допуская. Сделаем исходные допускающие состояния недо- пускающими. Тогда измененная МТ допускает L и работает столько же времени, сколь­ко М, с возможным добавлением одного перехода. Таким образом, L принадлежит V, если L принадлежит Т.

Неизвестно, замкнут ли класс NT относительно дополнения, но похоже, что нет. В ча­стности, можно ожидать, что если язык NP-полон, то его дополнение не принадлежит NP.

11Л .1. Класс языков со-MV

Co-NT— это класс языков, дополнения которых принадлежат NT. Напомним, что дополнение любого языка из Т также принадлежит Т и, следовательно, NT. С другой стороны, мы верим, что дополнения NP-полных проблем не принадлежат NT, поэтому в со-NT нет ни одной NP-полной проблемы. Аналогично мы верим, что дополнения NP- полных проблем, по определению содержащиеся в со -NT, не находятся в NP. На рис. 11.1 показана предполагаемая взаимосвязь этих классов. Однако не следует забы­вать, что если V окажется равным NP, то все три класса совпадут.

Пример 11.1. Рассмотрим дополнение языка ВЫП, которое принадлежит со-NP и обозначается НВЫП (невыполнимая). НВЫП включает все коды невыполнимых булевых формул, а также цепочки, которые не являются кодами допустимых булевых формул. Мы верим, что НВЫП не принадлежит NT, но доказать это не можем.

Еще одним примером проблемы, которая предположительно находится в со-MP, но не в MP, служит язык ТАВТ — множество всех (закодированных) булевых фор­мул, являющихся тавтологиями, т.е. истинных при любой подстановке. Заметим, что формула Е является тавтологией тогда и только тогда, когда -iЕ невыполнима. Таким образом, ТАВТ и НВЫП связаны так, что если булева формула Е принадлежит ТАВТ, то -1Е принадлежит НВЫП, и наоборот. Однако НВЫП содержит также цепоч­ки, не представляющие допустимые выражения, тогда как все цепочки в ТАВТ — до­пустимые. □

11.1.2. NP-полные проблемы и со-AfP

Предположим, что Р*МР. Возможно, ситуация, связанная с со-MP, отличается от представленной на рис. 11.1, поскольку MP и со -MP могут совпадать, но быть больше V. Таким образом, проблемы типа НВЫП или ТАВТ могли бы разрешаться за полиноми­альное недетерминированное время, т.е. принадлежать MP, не имея детерминирован­ного полиномиального решения. Однако отсутствие хотя бы одной NP-полной про­блемы, имеющей дополнение в MP, обосновывает, что MP * со -MP. Докажем это в следующей теореме.

Теорема 11.2. MP = со-МР тогда и только тогда, когда существует NP-полная про­блема, дополнение которой принадлежит MP.

Доказательство. (Необходимость) Если бы MP и со-МР совпадали, то каждая NP- полная проблема L находилась бы как в MP, так и в со-МР. Но дополнение проблемы из со -MP находится в MP, поэтому дополнение L принадлежало бы MP.

(Достаточность) Предположим, что Р — NP-полная проблема, дополнение Р кото­рой принадлежит MP. Тогда для любого языка L из MP существует полиномиальное све­дение L к Р. Это сведение является одновременно полиномиальным сведением L к Р . Докажем равенство классов MP и со -MP, показав их взаимное включение.

MP с со-MP. Пусть L принадлежит MP. Тогда L принадлежит со -MP. Объединим полиномиальное сведение L к Р с предполагаемым недетерминированным полиноми­альным алгоритмом для Р , чтобы получить такой же алгоритм для L . Тогда для любо­го L из MP его дополнение L также принадлежит MP. Следовательно, L, будучи допол­нением языка из MP, находится в со-МР. Отсюда MP с со -MP.

Со-MP с MP. Пусть L принадлежит со-МР. Тогда существует полиномиальное све­дение L к Р, поскольку Р является NP-полным, a L принадлежит MP. Это сведение яв­ляется также сведением L к Р. Поскольку Р принадлежит MP, объединим это сведение с недетерминированным полиномиальным алгоритмом для Р и убедимся, что L принад­лежит MP. □

11.1.3. Упражнения к разделу 11.1

• (!) Ниже представлено несколько проблем. Для каждой определите, принадле­жит онаMPили со-MP. Опишите дополнение каждой проблемы. Если проблема или ее дополнение являются NP-полными, докажите это.

а)   (*) Проблема ИСТ-ВЫП. По данной булевой формуле Е, истинной, когда все переменные имеют значение «истина», определить, существует ли еще одна подстановка, удовлетворяющая Е.

б)   Проблема ЛОЖЬ-ВЫП. Дана булева формула Е, ложная, когда все перемен­ные имеют значение «ложь». Определить, существует ли еще одна подста­новка, при которой Е ложна.

в)   Проблема ДВЕ-ВЫП. По данной булевой формуле Е определить, существу­ют ли хотя бы две подстановки, удовлетворяющие Е.

г)   Проблема ПОЧТИ-ТАВТ. Дана булева формула Е. Определить, является ли она ложной не более, чем при одной подстановке.

• (*!) Предположим, что существует взаимно однозначная функция/ которая отобра­жает одни «-битовые целые числа в другие и обладает следующими свойствами.
  • fix) можно вычислить за полиномиальное время.
  • f\x) нельзя вычислить за полиномиальное время.

Докажите, что в таком случае язык, состоящий из пар целых чисел (х, у), для которых

г\х)<у, ■

принадлежит (MP П со -MP) — V.

11.2. Проблемы, разрешимые в полиномиальном пространстве

Рассмотрим класс проблем, включающий MP и, возможно, еще больше, но уверенно­сти в этом нет. Этот класс определяется машинами Тьюринга, которые могут использо­вать объем пространства, полиномиальный относительно размера входа; время работы роли не играет. Вначале классы языков, допускаемых детерминированными и недетер­минированными МТ с полиномиальным ограничением пространства, различаются, но затем будет показано, что они совпадают.

Для полиномиального пространства существуют полные проблемы Р в том смысле, что все проблемы данного класса сводимы за полиномиальное время к Р. Таким образом, если Р принадлежит V или ЛfV, то все языки МТ с полиномиально ограниченным про­странством также принадлежат V или MP, соответственно. Мы представим пример такой проблемы — «булевы формулы с кванторами».

11.2.1. Машины Тьюринга с полиномиальным пространством

Машина Тьюринга с полиномиальным ограничением пространства представлена на рис. 11.2. Существует некоторый полином р(п), для которого МТ, имея вход w длиной п, не посещает более р(п) клеток ленты. Согласно теореме 8.12 можно считать, что лента является односторонней, а МТ не сдвигается влево от начала входа.

Конечное управление входи» л клеток -М— когда-либо используемые клетки р(п) клеток Рис. 11.2. МТ, использующая полиномиальное пространство

Класс языков VS (polynomial space — полиномиальное пространство) определяется как множество языков L(M) детерминированных МТ М с полиномиально ограниченным про­странством. Определим также класс MPS (nondeterministic polynomial space — недетерми­нированное полиномиальное пространство) как множество языков L(M) недетерминиро­ванных МТ М с полиномиально ограниченным пространством. Очевидно, VS с MVS, no­скольку каждая детерминированная МТ является недетерминированной. Будет доказан не­ожиданный результат: VS = MPS.^[1]

11.2.2. Связь VS и AfPS с определенными ранее классами

Отметим сразу, что включения V с VS и MP с MPS очевидны. Если МТ совершает по­линомиальное число переходов, то она использует не более, чем полиномиальное число кле­ток, точнее, число посещаемых ею клеток не более, чем на 1 превышает число переходов. До­казав, что ‘PS = HPS, мы убедимся в справедливости цепочки включений V с ЯР с VS.

Существенное свойство МТ с полиномиально ограниченным пространством состоит в том, что они могут совершить не более, чем экспоненциальное число переходов перед повто­рением МО. Этот факт нужен для доказательства других интересных результатов, касающих­ся VS, а также для того, чтобы показать, что VS содержит только рекурсивные языки, т.е. языки с алгоритмами. Отметим, что в определении VS или M’PS останов МТ не упоминается, т.е. МТ может зацикливаться, не выходя за пределы полиномиальной по объему части ленты.

Теорема 11.3. Если М— МТ с полиномиально ограниченным пространством, а р(п) — полиномиальный предел ее пространства, то существует константа с, при которой М, допуская свой вход w длиной п, делает это в пределах с^1+р(п) переходов.

Доказательство. Основная идея состоит в том, что М должна повторить МО перед тем, как совершить более с^1+р<п) переходов. Если М повторяет МО и затем допускает, то должна

существовать более короткая последовательность МО, ведущих к допусканию, т.е., ее- • * *

ли а |- /3 j— /3 |-у, где а— начальное, /3— повторяемое, а у— допускающее МО, то

^а Ь Р Ь У— более короткая последовательность МО, приводящая к допусканию.

В обосновании существования с используется то, что у МТ с ограниченным про­странством есть лишь ограниченное число МО. Точнее, пусть t— число ленточных сим­волов, а$ — состояний МТ М. Тогда число различных МО М, использующей р(п) клеток, не более spin)^, т.е. можно выбрать одно из s состояний, поместить ленточную головку в одну из р(п) позиций и заполнить р(п) клеток любой из t^p<n) последовательностей лен­точных символов.

Выберем с = s + t и раскроем бином (t + s)^1+p(n>:

Л^р(п) + (1 +p(n))st^m+… Заметим, что второе слагаемое не меньше sp(n)f»⁽ⁿ⁾; это доказывает, что с^1+р(п) не меньше числа возможных конфигураций М. Отметим, что, если М допускает вход w длиной п, то она выполняет последовательность переходов без повторения МО. Следовательно, М до­пускает, совершив переходов не больше с^1+р<п) — количества различных МО. □

Теорему 11.3 можно использовать для преобразования любой МТ с полиномиально ограниченным пространством в эквивалентную машину, которая всегда останавливается, совершив не более экспоненциального числа переходов. Зная, что МТ допускает в пре­делах экспоненциального числа переходов, можно подсчитать количество совершаемых переходов и остановить работу, не допуская, если сделано достаточно много переходов без допускания.

Теорема 11.4. Если L— язык из VS (MPS), то L допускается детерминированной (недетерминированной) МТ с полиномиально ограниченным пространством, которая для некоторого полинома д(п) и константы с останавливается После не более чем с^ч(п) переходов.

Доказательство. Докажем утверждение для детерминированных МТ. Для НМТ до­казательство аналогично. Пусть L допускается МТ М,, имеющей полиномиальное огра­ничение пространства р(п). Тогда по теореме 11.3, если Mi допускает w, то делает это в пределах c^1+p(‘^wl) шагов.

Построим новую МТ М₂ с двумя лентами. На первой ленте М₂ имитирует M_h а на второй ведет счет до с^1+р(‘^Л«, используя основание с. Если счет у М₂ достигает этого чис­ла, то она останавливается, не допуская. Таким образом, М₂ использует 1 + p(\w\) клеток второй ленты. Поскольку Mi использует не более р(И) клеток своей ленты, М₂ также ис­пользует не более р(Н) клеток первой ленты.

Преобразуя М₂ в одноленточную МТ М₃, можно гарантировать, что М₃ использует не более 1 + р(п) клеток ленты при обработке любого входа длиной п. Хотя М₃ может ис­пользовать квадрат времени работы М₂, это время не превышает 0(с^2р(п>).^[2]

МТ М₃ совершает не более dc^2p(n) переходов для некоторой константы d, поэтому можно выбрать q(ri) = 2р(п) + log_cd. Тогда М₃ совершает не более с^ч(п) шагов. М₂ всегда останавливается, поэтому то же делает М₃. Mi допускает L, поэтому его же допускают М₂ и М₃. Таким образом, М₃ удовлетворяет утверждению теоремы. □

11.2.3. Детерминированное и недетерминированное полиномиальное пространство

Сравнение классов V и MP затруднительно, но, на удивление, сравнить классы VS и MPS легко — они совпадают. Доказательство основано на имитации недетерминирован­ной МТ, пространство которой ограничено полиномом р(п), с помощью детерминиро­ванной МТ, имеющей ограничение пространства 0(р²(п)).

«Сердцем» доказательства является детерминированная рекурсивная проверка, может ли НМТ N перейти от МО I к МО J не более, чем за /и переходов. ДМТ D систематически прове­ряет все промежуточные МО К, чтобы убедиться, может ли N перейти от / к К за т/2 перехо­дов, а затем перейти от К к J за /и/2 переходов. Итак, представим, что существует рекурсивная

*

функция reach(l, J, т), решающая, верно ли, что / |- J не более, чем за /и/2 переходов.

Рассмотрим ленту машины D как магазин, в который помещаются аргументы рекур­сивных вызовов функции reach, т.е. один элемент магазина хранит [/, J, /и]. Алгоритм функции reach представлен на рис. 11.З.^[3]

BOOLEAN FUNCTION reach(I, J, m) ID: I,J; INT: m; BEGIN

IF (m == 1) THEN /* базис */ BEGIN

проверить, что I == J или I может стать J за 1 переход; если так, RETURN TRUE, иначе RETURN FALSE;

END;

ELSE /* индуктивная часть */ BEGIN FOR каждая возможная МО К DO

IF (reach(I,K,m/2) AND reach(K,J,m/2)) THEN RETURN TRUE; RETURN FALSE;

END; END;

Puc. 11.3. Рекурсивная функция reach проверяет, можно ли за установленное число переходов перейти от одного МО к другому

Важно заметить, что, хотя reach вызывает саму себя дважды, она делает это последо­вательно, поэтому в любой момент времени активен лишь один вызов. Таким образом, если начать с элемента магазина [lj, J_h /и], то в любой момент времени существует толь­ко один вызов [I₂, J?, т/2], один вызов [/j, J₃, т/4], еще один [1₄, J₄, т/8] и так далее, пока в некоторой точке третий аргумент не станет равным 1. В этот момент reach может при­менить базисный шаг и не нуждается в рекурсивных вызовах. Она проверяет, верно ли, что / |- J или / = J, и возвращает true, если это так, и false — если нет. На рис. 11.4 представлен общий вид магазина ДМТ D, когда существует столько активных вызовов reach, сколько возможно при начальном количестве переходов т.

Рис. 11.4. Лента ДМТ, имитирующей НМТ с помощью рекурсивных вызовов reach

Хотя может показаться, что возможно много вызовов функции reach, и лента, изобра­женная на рис. 11.4, может стать очень длинной, мы докажем, что она не будет «слишком длинной», т.е., если начать с числа переходов т, то в любой момент времени на ленте не может быть более log? т элементов магазина. Поскольку теорема 11.4 гарантирует, что НМТ N не может совершить более с^р(п) переходов, начальное значение т также не пре­вышает Таким образом, число элементов магазина не превосходит log, с^т\ т.е. 0{р(п)), и у нас есть все необходимое для доказательства следующей теоремы.

Теорема 11.5 (теорема Сэвича). VS = MVS.

Доказательство. Очевидно, что VS с MVS, поскольку каждая ДМТ является также и НМТ. Таким образом, достаточно доказать, что MVS с VS, т.е., если L допускается НМТ N с ограничением пространства р(п), где р(п) — полином, то L также допускается ДМТ Д пространство которой ограничено другим полиномом q(n). В действительности будет показано, что q(ri) можно выбрать равным по порядку квадрату р{п).

По теореме 11.3 можно предполагать, что, если N допускает, то делает это в преде­лах с^1+р(п) шагов, где с — некоторая константа. Получив вход w длиной п, D исследует, что делает N со входом w, многократно помещая тройки вида [I₀, J, т\ на свою ленту и вызывая reach с этими аргументами. Здесь 1₀ является начальным МО машины N со входом w, J— некоторое допускающее МО, в котором используется не более р(п) кле­ток (различные J систематически перечисляются машиной D с помощью рабочей лен­ты), а т = с^1+р(п).

Выше было обосновано, что рекурсивных вызовов, активных одновременно, не мо­жет быть более log₃ да, т.е. один с аргументом т, один с аргументом т/2, один с аргумен­том т/4 и так далее до 1. Таким образом, существует не более log₂ т элементов магазина, a log₂ т есть 0(р(п)).

Элементы магазина сами по себе занимают пространство 0(р(п)). Причина в том, что для записи каждого МО нужно 1 + р(п) клеток, а для записи т в двоичном виде — log₂c^1+p(n), т.е. 0(р(п))

клеток. Таким образом, полный элемент магазина, состоящий из двух МО и целого числа, занимает пространство 0(р(п)).

Поскольку D может иметь не более 0(p(ri)) элементов магазина, общее количество используемого пространства составляет 0(р²(п)). Это количество полиномиально, если р(п) — полином, и мы делаем вывод, что L имеет ДМТ с полиномиально ограниченным пространством. □

В заключение можно уточнить информацию о классах сложности, включая классы с по­линомиально ограниченным пространством. Полная диаграмма представлена на рис. 11.5.

11.3. Проблема, полная для VS

В этом разделе представлена проблема, которая называется «булевы формулы с кван­торами», и показано, что она полна для VS.

Рекурсивные

Рис. 11.5. Известные соотношения между классами языков

11.3.1. PS-полнота

Проблема Р определяется как полная для VS (PS-полная), если выполняются следую­щие условия.

Р принадлежит VS.

Все языки L из VS полиномиально сводимы к Р.

Отметим, что условия PS-полноты похожи на условия NP-полноты — сведение должно выполняться за полиномиальное время. Это позволило бы установить, что V = VS, если бы какая-нибудь PS-полная проблема оказалась в V, и что MV = VS. если бы она оказа­лась в MP. Если бы сведения были лишь в полиномиальном пространстве, то размер вы­хода мог бы быть экспоненциальным относительно размера входа, и невозможно было бы прийти к заключению следующей теоремы. Но, ограничившись сведениями, полино­миальными по времени, получаем желаемые взаимосвязи. Теорема 11.6. Пусть Р — PS-полная проблема. Тогда:

а)   если Р принадлежит V,toV = VS\

б)   если Р принадлежит MP, то MP = VS.

Доказательство. Докажем вариант а. Для любого L из VS известно, что существует полиномиальное (по времени) сведение L к Р. Пусть оно занимает время q(n). Предпо­ложим, Р принадлежит V и имеет алгоритм с полиномиальным временем, например р(п).

По данной цепочке w, принадлежность которой языку L мы хотим проверить, можно, используя сведение, получить цепочку х, находящуюся в Р тогда и только тогда, когда w

принадлежит L. Поскольку сведение занимает время q(\w\), цепочка х не может быть длиннее, чем <7(И). Принадлежность х языку Р можно проверить за время р(|х|), т.е. p(q(\w\)), полиномиальное относительно (н’|. Приходим к выводу, что для L существует полиномиальный алгоритм.

Следовательно, каждый язык L из VS принадлежит V. Поскольку включение V в VS очевидно, приходим к выводу, что если Р принадлежит V, то V = VS. Доказательство пункта б, где Р принадлежит AfV, аналогично и оставляется читателю.

11.3.2. Булевы формулы с кванторами

Продемонстрируем проблему Р, полную для VS. Но сначала нужно изучить термины, в которых формулируется эта проблема, называемая «булевы формулы с кванторами» (quantified boolean formulas), или КБФ.

Грубо говоря, булева формула с кванторами — это булево выражение с добавлением операторов V («для всех») и 3 («существует»). Выражение (Vx)(E) означает, что Е истин­но, если все вхождения х заменить 1 (истина), а также, если все вхождения х заменить О (ложь). Выражение (Эх)(£) означает, что Е истинно, если или все вхождения х заменить 1, или все вхождения х заменить 0, или в обоих случаях.

Для простоты описания предположим, что ни одна КБФ не содержит двух и более квантификаций (V или 3) одной и той же переменной х. Это ограничение не является существенным, и соответствует, грубо говоря, запрещению того, чтобы две различные функции в программе использовали одну и ту же локальную переменную^[4]. Формально, булевы формулы с кванторами (КБФ) определяются следующим образом.

О (ложь), 1 (истина) или любая переменная являются КБФ.

Если Е и F — КБФ, то КБФ являются (Е), -,(£), (Е) л (F) и (Е) v (F), представляя Е в скобках, отрицание Е, логическое И Е и F и логическое ИЛИ En F, соответственно. Скобки можно опускать, если они избыточны, используя обычные правила приори­тета (старшинства): НЕ, затем И, затем ИЛИ. Часто используется «арифметический» стиль представления И и ИЛИ, когда И представлен непосредственным соседством (знак операции отсутствует), а ИЛИ — знаком +. Таким образом, вместо (Е) л (F) часто используется (E)(F), а вместо (Е) v (F) — (Е) + (F).

Если Е — КБФ без квантификации переменной х, то (Vx)(E) и (Эх)(£) — КБФ. При этом говорят, что областью действия переменной х является выражение Е. Нефор­мально говоря, х определена только в пределах Е, подобно тому, как областью дей­ствия (определения) переменной в программе является функция, в которой эта пере­менная определена. Скобки вокруг Е (но не вокруг квантификации) можно удалить, если не возникает неоднозначности. Однако во избежание нагромождения вложен­ных скобок цепочка квантификаций вида

(Vx)((3y)((Vz)(£)))

записывается только с одной парой скобок вокруг Е, а не с парой для каждой кван­тификации в цепочке, т.е. в виде (Vx)(3y)(Vz)(£).

Пример 11.7. Рассмотрим пример КБФ:

(Vx)((3y)(xy) + (Vz)(—ix + z)).                                                      (11.1)

Сначала переменные х и у связываются операцией И, затем применяется квантор (Зу) для получения подвыражения (Зу)(ху). Аналогично строится булево выражение —ct + z и применяется квантор (Vz) для получения подвыражения (Vz)(—а + z). Далее эти выраже­ния становятся операндами ИЛИ; скобки в выражении не нужны, поскольку + (ИЛИ) имеет минимальный приоритет. Наконец, к этому выражению применяется квантор (Vx) и получается вся указанная КБФ. □

11.3.3. Вычисление булевых формул с кванторами

Определим формально значение КБФ. Интуитивную идею для этого дает прочте­ние V как «для всех», а 3 — как «существует». КБФ (11.1) утверждает, что для всех х (т.е. х = 0 или х = 1) существует у, при котором как х, так и у истинны, или же для всех z истинно —я + z. Это утверждение оказывается истинным. Если х = 1, то можно выбрать у = 1 и сделать ху истинным. Если же х = 0, то —а: + z истинно для обоих значений z.

Если переменная х находится в области действия некоторой квантификации х, то это вхождение х называется связанным, в противном случае — свободным.

Пример 11.8. Каждое использование переменной в КБФ (11.1) является связанным, поскольку находится в области действия квантора с этой переменной. Например, область действия переменной у, квантифицированной в (Зу)(ху), — это выражение ху. Таким об­разом, данное вхождение у связано. Вхождение х в ху также связано из-за квантора (Vx), областью действия которого является все выражение. □

Значением КБФ без свободных переменных является или 0, или 1 (ложь или истина, соответственно). Значение такой КБФ можно вычислить с помощью индукции по длине п выражения.

Базис. Если длина выражения 1, то оно может быть только константой 0 или 1 (любая переменная была бы свободной). Значением выражения является оно само.

Индукция. Пусть дана КБФ длиной п > 1 без свободных переменных, и можно вы­числить любое выражение меньшей длины, если в нем нет свободных переменных. Воз­можны 6 видов такой КБФ.

(£). Тогда £ имеет длину п-2, и значение Е может быть вычислено как 0 или 1. Значение (£) совпадает с ним.

—IЕ. Тогда Е имеет длину п- 1 и его значение можно вычислить. Если £=1, то —I£ = 0, и наоборот.

1. Выражения £ и £ короче п и могут быть вычислены. Значением EF будет 1, если оба выражения £ и £ имеют значение 1, и 0, если хотя бы одно из них равно 0.

£ + £. Выражения £ и £ короче п и могут быть вычислены. Значением £ + £ будет 1, если хотя бы одно из £ и £ имеет значение 1, и 0, если оба равны 0.

(Vx)(£). Все вхождения х в £ заменяются значением 0 для получения выражения £₀, а также все вхождения х в £ заменяются значением 1 для получения Е,. Заметим, что выражения Е₀ и £_;:

а)   не имеют свободных переменных, поскольку любое вхождение свободной переменной отличалось бы от х и было бы свободным в £;

б)   имеют длину п — 6, что меньше п.

Вычисляются Е₀ и £,. Если у обоих значение 1, то (Vx)(£) имеет значение 1; в про­тивном случае — 0. Отметим, каким образом это правило отражает интерпретацию (Vx) с помощью «для всех х».

(Зх)(£). Как и в п. 5, строятся и вычисляются Е₀ и £_;. Если хотя бы у одного из них значение 1, то значением (Зх)(£) будет 1; в противном случае— 0. Отметим, каким образом это правило отражает интерпретацию (Эх) с помощью «существует х».

Пример 11.9. Вычислим КБФ (11.1). Она имеет вид (Vx)(£), поэтому сначала

(11.2)

(11.3)

вычислим Е₀:

(3y)(0y) + (Vz)(-.0 + z).

Значением этого выражения будет 1, если хотя бы один из операндов ИЛИ — (Зу)(()у) и (Vz)(—10 + z) — имеет значение 1. Для вычисления (3у)(0у) нужно подставить у = 0 и у = 1 в подвыражение 0у и проверить, что хотя бы одно из двух получаемых выражений имеет значение 1. Однако и 0 л 0, и 0 л 1 имеют значение 0, поэтому значением (Эу)(0у) будет О.^[5]К счастью, значением (Vz)(—.0 + z) будет 1 — это видно при подстановке г = 0 и г = 1. Поскольку —10 — 1, в этих двух случаях вычисляется lvO и 1 v 1, т.е. 1. Поэтому (Vz)(—10 + z) имеет значение 1. Итак, значением Е₀, т.е. выражения (11.2), является 1. Еще нужно также проверить, что выражение £_; —

(3y)(ly) + (Vz)bl+z),
получаемое при подстановке х = 1 в (11.1), также имеет значение 1. Значением выраже­ния (Зу)(1у) будет 1, что видно при подстановке у = 1. Таким образом, Е/, т.е. выражение (11.3), имеет значение 1, и значением всего выражения (11.1) является 1. □

11.3.4. PS-полнота проблемы КБФ

Теперь определим проблему формулы с кванторами: выяснить, имеет ли данная КБФ без свободных переменных значение 1. Эта проблема сокращенно обозначается КБФ, хотя КБФ продолжает применяться и как сокращение для термина «булева формула с кванторами». Контекст всегда позволит избежать двусмысленности.

Будет показано, что проблема КБФ полна для VS. Доказательство сочетает идеи тео­рем 10.9 и 11.5. Из теоремы 10.9 берется идея представления вычисления МТ с помощью логических переменных, каждая из которых говорит, имеет ли определенная клетка опре­деленное значение в определенный момент времени. Однако в теореме 10.9 речь шла о по­линомиальном времени, поэтому там присутствовало полиномиальное количество пере­менных. Мы были в состоянии за полиномиальное время породить выражение, говорив­шее, что МТ допускала свой вход. Когда же речь заходит о полиномиальном пространстве, число МО в вычислении может быть экспоненциальным относительно размера входа, по­этому за полиномиальное время записать выражение, говорящее о корректности вычисле­ния, невозможно. К счастью, теперь у нас есть более мощный язык, и возможность кванти­фикации позволяет записать полиномиальную по длине КБФ, которая говорит, что МТ с полиномиально ограниченным пространством допускает свой вход.

Для выражения идеи того, что одно МО превращается в другое за некоторое большое число переходов, из теоремы 11.5 берется принцип «рекурсивного дублирования». Для того чтобы сказать, что МО I превращается в МО J за т переходов, утверждается, что существу­ет МО К, получаемое из 1 за /и/2 переходов и приводящее к J еще за /и/2 переходов. Язык булевых формул с кванторами позволяет выражать такого рода факты в пределах полино­миальной длины, даже если т экспоненциально относительно длины входа.

Перед проведением доказательства, что каждый язык из VS полиномиально сводим к КБФ, нужно показать, что КБФ принадлежит VS. Эта часть доказательства PS-полноты сама по себе сложна и выделяется в следующую теорему.

Теорема 11.10. КБФ принадлежит VS.

Доказательство. В разделе 11.3.3 был описан рекурсивный процесс вычисления КБФ F. Этот алгоритм можно реализовать с использованием магазина, хранимого на ленте МТ, как в доказательстве теоремы 11.5. Пусть п — длина F. Тогда для F создается запись длиной 0(п), включающая саму F и пространство для записи обрабатываемых подвыражений F. Процесс вычисления объясняется для двух из шести возможных вари­антов выражения F.

1. Пусть F = F, + Fj. Тогда выполняем следующее:

а)  помещаем F, в ее собственную запись справа от записи для F;

б)  рекурсивно вычисляем F,\

в)   если значением F, является 1, то возвращаем 1 как значение F;

г)   если значение F_s — 0, то ее запись замещаем записью для F₂ и рекурсивно вычисляем F₂,

д)   в качестве значения F возвращаем значение F₂. 2. Пусть F= (3х)(Е). Тогда выполняем следующее:

а)  создаем выражение Е₀ путем подстановки 0 вместо каждого вхождения х и помещаем Е_п в собственную запись справа от записи для F;

б)  рекурсивно вычисляем Е₀\

в)   если значением Е₀ является 1, то возвращаем 1 как значение F;

г)   если значение Е₀ — 0, то создаем выражение E_h подставляя 1 вместо х в Е\

д)  запись для Е₀ замещаем записью для Ei и рекурсивно вычисляем E_s\

е)   в качестве значения F возвращаем значение Е,.

Описание подобных шагов вычисления F в ее остальных четырех формах — F_SF₂, —Е, (Е), (\/х)(Е)— предоставляется читателю. Базисный случай, когда формула является константой, требует лишь возвращения этой константы без создания записей на ленте.

Заметим, что в любом случае справа от записи для выражения, длина которого т, присутствует запись для выражения меньшей длины. Отметим, что, хотя в случае 1 вы­числяются два различных подвыражения F, и F₂, это делается последовательно. Таким образом, записи для F_s и его подвыражений и записи для F₂ и его подвыражений не при­сутствуют на ленте одновременно. То же верно и для Е₀ и в п. 2.

Следовательно, если мы начинаем с выражения длиной п, в магазине не может быть более п записей. Каждая запись имеет длину О(п). Поэтому размер ленты не превышает 0(п²). Теперь у нас есть конструкция для МТ с полиномиально ограниченным простран­ством, допускающей КБФ; предел ее пространства является квадратичным. Заметим, что время работы этого алгоритма обычно экспоненциально относительно п, поэтому он не полиномиален по времени. □

Обратимся к сведению произвольного языка L из VS к проблеме КБФ. Нам хотелось бы использовать пропозициональные переменные y,_jA, как в теореме 10.9, для утвержде­ния, что в j-й позиции г-го МО находится символ А. Однако, поскольку МО экспоненци­альное число, нельзя взять вход длиной п и даже просто выписать эти переменные за время, полиномиальное относительно п. Воспользуемся квантификацией, чтобы с помо­щью одного и того же множества переменных представлять много различных МО. Эта идея раскрывается в доказательстве следующей теоремы. Теорема 11.11. Проблема КБФ PS-полна.

Доказательство. Пусть L — язык из VS, допускаемый недетерминированной МТ М, которая при обработке входа длиной п использует не более р(п) клеток. По теореме 11.3 существует константа с, для которой М допускает вход длиной п в пределах с^1+р(п) пере­ходов (если допускает). Опишем, как за полиномиальное время по входу w длиной п по­строить КБФ Е без свободных переменных, имеющую значение 1 тогда и только тогда, когда w принадлежит ЦМ).

При записи Е нам понадобится ввести полиномиальное число переменных МО, кото­рые представляют собой множества переменных y_jA, утверждающих, что j-я позиция представляемого МО содержит символ А (/’ может изменяться от 0 до р(п)). А есть либо ленточный символ, либо состояние М. Таким образом, число пропозициональных пере­менных в переменном МО полиномиально относительно п. Предположим, что все про­позициональные переменные в разных переменных МО различимы, т.е. ни одна из них не принадлежит двум разным переменным МО. Поскольку существует лишь полиноми­альное число переменных МО, общее количество пропозициональных переменных по­линомиально.

Удобно ввести нотацию (3/), где I— переменное МО. Этот квантор записывается вместо (3х/)(3х₂)…(3х_ш), где x_h х₂, …, х_т — все пропозициональные переменные в пере­менном МО I. Аналогично вместо применения квантора V ко всем пропозициональным переменным в / записывается (V7).

КБФ, которая строится для w, имеет вид

(3I₀)(3I_f)(S л N л F)-

Подвыражения этой формулы имеют следующий смысл.

/₀ и I, — переменные МО, представляющие начальное и допускающее МО, соответ­ственно.

S— выражение, говорящее о «правильном старте», т.е. что 1₀ действительно являет­ся начальным МО Мсшна входе.

N— выражение, которое говорит о «правильных переходах», совершаемых М при преобразовании 1₀ к //.

F— выражение, говорящее о «правильном финише», т.е. что If является допускаю­щим МО.

Отметим, что хотя выражение в целом не имеет свободных переменных, переменные из 1„ будут появляться как свободные в S, переменные из If— как свободные в F, а обе группы переменных будут свободны в N. Правильный старт

S является логическим И литералов; каждый литерал — это одна из переменных МО I₀. S имеет литерал y_jA, если в j-й позиции начального МО со входом w находится символ А, и литерал у_/А , если нет. Таким образом, если w = а,а₂…а„, то у„_чп, у_/а/, у_2а2, Ую„ и все у,н для j = п + 1, п + 2, …, р(п) появляются без отрицания, а все остальные перемен­ные МО 1₀ — с отрицаниями. Здесь предполагается, что q₀ — начальное состояние М, а В — пробел.

Правильный фиииш

If является допускающим МО, если содержит допускающее состояние. Следователь­но, F записывается как логическое ИЛИ тех переменных y_jA, выбранных из пропозицио­нальных переменных МО If, для которых А является допускающим состоянием. Позиция j произвольна.

Правильные переходы

Выражение N строится рекурсивно с помощью метода, который позволяет удвоить число рассматриваемых переходов, добавив лишь 0(р(п)) символов в конструируемое выражение и (что важнее) затратив для написания выражения время 0(р(п)). Для логиче­ского И выражений, в которых приравниваются соответствующие переменные МО / и J, полезно использовать сокращение I = J. Таким образом, если I состоит из переменных y_jA и J состоит из переменных z_jA, то I = J— это И выражений (у_;А z_jA + y_jA z_jA ), где j изме­няется от 0 до р(п), а А — любой ленточный символ или состояние М.

Теперь для обозначения того, что 11- J за i или менее переходов, построим выражения N,{I,J), где /’= 1, 2, 4, 8,…. В этих выражениях свободны только пропозициональные пере­менные переменных МО / и J; все остальные пропозициональные переменные связаны.

Такое построение N_2i не работает

Первым инстинктивным побуждением, связанным с построением N_2i по N„ может

быть непосредственное применение подхода «разделяй и властвуй»: если I |~ J за 2/

* *

или менее переходов, то должно существовать МО К, для которого / [- К и К [- J за i или менее переходов. Однако, если записать формулу, которая выражает эту идею, например, N₂,(I, J) — (3A’)(iV,(/, К) л N,(K, J)), то длина выражения удвоится при удвое­нии /’. Чтобы выразить все возможные вычисления М, i должно быть экспоненциаль­ным относительно п, поэтому для написания N будет затрачено слишком много вре­мени, и N будет иметь экспоненциальную длину.

Базис. Для i = 1 выражение N,(I, J) устанавливает, что I = J или I \- J. Мы только что обсудили, как выразить условие I = J. Для условия I ]- J сошлемся на часть «правильные переходы» из доказательства теоремы 10.9, где также возникала проблема утверждения, что очередное МО следует из предыдущего. Выражение N_t является логическим ИЛИ этих двух выражений. Заметим, что оно записывается за время 0(р(п)).

Индукция. По N, построим N₂,(I, J). Во врезке «Такое построение N_2i не работает» отмечается, что прямой метод построения N_2i с помощью двух копий N, не дает нужного времени и пространства. Корректный способ записи N_2i состоит в том, чтобы в выраже­нии записывать одну копию N_h подставляя как (/, К), так и (К, J) в одно и то же выраже­ние. Таким образом, в N₂,(I, J) используется одно подвыражение N,{P, Q). N₂,(L J) запи­сывается для утверждения, что существует МО К, при котором для всех МО Р и Q вы­полняется хотя бы одно из следующих условий.

(Р, Q) * (/, К) и (Л Q) * (К,.]).

N,(P, Q) истинно.

Иными словами, N,(1, К) и N,(K, J) истинны, а для других пар МО (Р, Q) истинность N,(P, Q) не имеет значения. Итак, КБФ для N₂,(I, J) имеет следующий вид.

N₂,(I, J) = (3/O(V/>)(V0W(A 0 V Ы1 = Р Л К = Q) Л Ч(К = Р A J = 0)) Отметим, что на запись N_2i уходит время, необходимое для записи N„ а также 0(р(п)) для дополнительной работы.

Чтобы завершить построение N, нужно записать N_m для наименьшего т, которое яв­ляется степенью 2 и не меньше с^1+р(п) — максимально возможного числа переходов, со­вершаемых МТ М перед тем, как допустить вход w длиной п. Количество применений шага индукции, описанного выше, равно log₂(c^1+p(n)), или 0(р(п)}. Поскольку каждое ис­пользование шага индукции занимает время 0{р{п)), приходим к выводу, что N можно построить за время 0(р²(п)).

Завершение доказательства теоремы 11.11 Выше показано, как преобразовать вход w в КБФ

(3l₀)(3I_f)(S л N л F)

за время, полиномиальное относительно |w|. Обосновано также, почему выражения S, N и F истинны тогда и только тогда, когда их свободные переменные представляют МО /₀ и

If, которые являются начальным и заключительным МО в вычислении М со входом w, *

причем I₀ [- If. Таким образом, данная КБФ имеет значение 1 тогда и только тогда, когда М допускает w. □

11.3.5. Упражнения к разделу 11.3

Дополните доказательство теоремы 11.10, рассмотрев варианты.

а)   F= F, F₂,

б)   F=(Vx)(£);

в)   F = —1(£);

г)   F=(E).

(*!!) Докажите, что следующая проблема является PS-полной. По данному регу­лярному выражению Е определить, эквивалентно ли оно £*, где Е — множество символов, встречающихся в Е. Указание. Вместо сведения КБФ к данной про­блеме можно показать, что любой язык из VS сводится к ней. Для каждой МТ М с полиномиально ограниченным пространством покажите, как взять вход w для М и построить за полиномиальное время регулярное выражение, порождающее все цепочки, которые не являются последовательностями МО машины М, веду­щими к допусканию w. 11.3.3. (!!) Переключательная игра Шеннона состоит в следующем. Дается граф G с двумя терминальными узлами sh/. Есть два игрока, называемых SHORT и CUT. По очереди каждый игрок выбирает узел графа G, не равный s и t, который до конца игры будет принадлежать этому игроку. Игру начинает SHORT. Он выиг­рывает, если выбирает множество узлов, которое вместе с s и t образует путь в графе G из s в /. CUT выигрывает, если все узлы выбраны, но SHORT не выбрал путь в графе G из s в t. Покажите PS-полноту проблемы: по данному графу G определить, может ли SHORT выиграть независимо от ходов CUT.

11.4. Классы языков, основанные на рандомизации

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

В этом разделе определяется тип машины Тьюринга, моделирующей генерацию слу­чайных чисел и их использование в алгоритмах. Далее определяются два класса языков, 7ZP и ZW, использующих эту случайность и полиномиальное время различными спосо­бами. Может показаться, что эти классы содержат совсем немного проблем вне V, одна­ко их отличие от Р весьма важно. В частности, в разделе 11.5 будет показано, почему не­которые наиболее существенные проблемы, связанные с безопасностью компьютеров, в действительности являются вопросами о соотношении этих классов с классами Р и MP.

11.4.1. Быстрая сортировка — пример рандомизированного алгоритма

Возможно, читатель знаком с алгоритмом сортировки, который называется «Быстрая сортировка» («Quicksort»). Сущность алгоритма такова. Из сортируемого списка элемен­тов a_h а₂, …, а„ выбирается один, скажем, a_h и элементы списка делятся на те, которые меньше или равны a_h и на те, которые больше a_h Выбираемый элемент называется ве­дущим (pivot). Тщательный подбор представления данных позволяет разделить список длиной п на два за время О(п). Далее можно рекурсивно отсортировать по отдельности список нижних (которые меньше или равны ведущему) и список верхних (больше веду­щего) элементов и в результате получить отсортированный список из всех п элементов.

Если нам повезет, то ведущий элемент окажется числом в середине сортируемого списка, и оба подсписка будут иметь длину примерно л/2. Если нам повезет на каждом рекурсивном шаге, то после примерно log₂ п уровней рекурсии у нас будут уже отсорти­рованные списки длиной 1. Таким образом, каждый из 0(log п) уровней требует О(п) времени, а вся работа — 0(п log п).

Однако нам может не повезти. Например, если список изначально отсортирован, то выбор первого элемента в каждом списке делит его на нижний подсписок с одним этим элементом и верхний — со всеми остальными. В данном случае быстрая сортировка ве­дет себя, как сортировка выбором, и при упорядочении п элементов занимает время, пропорциональное я².

Таким образом, хорошие реализации быстрой сортировки не выбирают механически никаких определенных позиций в списке для ведущих элементов. Ведущий элемент выби­рается в списке случайно, т.е. вероятность выбора каждого из п элементов в качестве веду­щего равна 1 /п. Ожидаемое время выполнения быстрой сортировки с использованием та­кой рандомизации равно 0(п log и), хотя данное утверждение-здесь не доказывается.^[6] Одна­ко из-за ненулевого шанса того, что каждый ведущий элемент окажется наибольшим или наименьшим, время выполнения быстрой сортировки в худшем случае остается 0(п²). Тем не менее, быстрая сортировка является основным методом сортировки во многих приложе­ниях (например, в UNIX), поскольку ожидаемое время ее выполнения в действительности гораздо меньше, чем у других методов, имеющих 0(п log п) в худшем случае.

11.4.2. Вариант машины Тьюринга с использованием рандомизации

Для того чтобы абстрактно представить способность машин Тьюринга к совершению случайного выбора, похожего на вызов генератора случайных чисел в программе, ис­пользуем вариант многоленточной МТ, изображенный на рис. 11.6. Первая лента, как обычно для многоленточных машин, содержит вход. Вторая лента также начинается не­пустыми клетками. В принципе, вся она содержит символы 0 и 1, выбранные с вероятно­стью 1/2. Вторая лента называется случайной лентой. Третья и последующие, если ис­пользуются, вначале пусты и при необходимости выступают как рабочие. Данный вари­ант МТ называется рандомизированной машиной Тьюринга.

Рис. 11.6. Машина Тьюринга, использующая случайно «генерируемые» числа

Поскольку нереалистично считать, что бесконечную ленту рандомизированной МТ можно вначале случайно заполнить символами 0 и 1, эквивалентный взгляд на такую МТ состоит в том, что ее лента изначально пуста. Однако далее, когда вторая головка обо­зревает пробел, происходит встроенное «бросание монеты», и рандомизированная МТ немедленно записывает символ 0 или 1 в обозреваемую клетку, не изменяя его в даль­нейшем. При таком способе отсутствует бесконечная работа, которую нужно было бы совершить перед началом работы рандомизированной МТ. Тем не менее, вторая лента оказывается покрытой случайными символами 0 и 1, поскольку эти случайные биты по­являются везде, где в действительности побывала головка второй ленты МТ.

Пример 11.12. Рандомизированную версию быстрой сортировки можно реализо­вать с помощью МТ. Важным шагом является следующий рекурсивный процесс. Предположим, что подсписок сохранен в последовательных клетках входной ленты и выделен маркерами с обоих концов. В подсписке выбирается ведущий элемент, и под­список делится на нижний и верхний подподсписки. Рандомизированная МТ выполня­ет такие действия.

• Пусть разделяемый подсписок имеет длину т. Используем до log₂ т новых случай­ных битов на второй ленте, чтобы выбрать случайное число между 1 и т\ т-й эле­мент подсписка становится ведущим. Отметим, что, возможно, вероятности выбора чисел от 1 до т не равны, поскольку т может не быть степенью 2. Однако, если взять, например, [2 log₂ т\ битов с ленты 2, рассмотреть их как число в диапазоне от О до т², взять остаток от деления на т и прибавить 1, то все числа от 1 до т будут иметь вероятность, достаточно близкую к Ут, чтобы быстрая сортировка выполня­лась корректно.
• Поместить ведущий элемент на ленту 3.
• Просмотреть список, выделенный на ленте 1, копируя элементы, которые не больше ведущего, на ленту 4.
• Снова просмотреть подсписок на ленте 1, копируя элементы, которые больше веду­щего, на ленту 5.
• Скопировать ленты 4 и затем 5 в пространство на ленте 1, ранее занятое выделен­ным подсписком. Поместить маркер между двумя подподсписками.
• Если подподсписки (хотя бы один из них) содержат более одного элемента, рекур­сивно отсортировать их по этому же алгоритму.

Заметим, что данная реализация быстрой сортировки требует 0(п log п) времени, хотя вычислительным устройством является МТ, а не обычный компьютер. Однако главное в этом примере — не время работы, а использование случайных битов на второй ленте для организации случайного поведения машины Тьюринга. □

11.4.3. Язык рандомизированной машины Тьюринга

Нам привычна ситуация, в которой машина Тьюринга (в частности, КА или МП- автомат) допускает некоторый язык, даже если он пуст или совпадает со всем множест­вом цепочек во входном алфавите. Имея дело с рандомизированными МТ, нужно быть более аккуратным с тем, что значит допускание входа такой машиной; становится воз­можным, что МТ вообще не допускает никакого языка. Проблема в том, что при анализе действий рандомизированной МТ М со входом w приходится рассматривать все возмож­ные случайные последовательности на второй ленте. Вполне возможно, что МТ допуска­ет при одних случайных последовательностях, но отвергает при других; в действитель­ности, если рандомизированная МТ должна делать что-то более эффективно, чем детер­минированная МТ, то существенно, чтобы различные последовательности на рандомизированной ленте приводили к различному поведению.^[7]

Если считать, что рандомизированная МТ допускает, достигая, как обычная МТ, за­ключительного состояния, то каждый вход w рандомизированной МТ имеет некоторую вероятность допускания, зависящую от содержимого случайной ленты, приводящего к допусканию. Поскольку экземпляров такого содержимого бесконечно много, при вычис­лении этой вероятности нужно быть осторожным. Вместе с тем, в любой последователь­ности переходов, приводящей к допусканию, используется лишь конечная часть случай­ной ленты, поэтому вероятность любой случайной последовательности равна 2~^т, если т — число клеток случайной ленты, когда-либо просмотренных и повлиявших на пере­ходы МТ. Следующий пример иллюстрирует вычисления в одном очень простом случае.

Пример 11.13. Функция переходов рандомизированной МТ М представлена на рис. 11.7. М использует только входную и случайную ленты. Она ведет себя очень про­сто, не изменяя ни одного символа на лентах и сдвигая головки только вправо (направление R) или оставляя на месте (S). Хотя формально запись переходов рандоми­зированной МТ не была определена, содержимое таблицы на рис. 11.7 должно быть по­нятно. Каждая строка таблицы соответствует состоянию, а каждая колонка — паре сим­волов XY, где X— символ, обозреваемый на входной ленте, a Y— на случайной. Клетка qUVDE таблицы означает, что МТ переходит в состояние q, записывает U на входной ленте, V— на случайной, сдвигает головку на входной ленте в направлении Д а на слу­чайной — в направлении Е.

	00	01	10	11	BO	B\
	qfiORS	q30lSR	q2\0RS	qrjllSR
4i	qfiORS				q4B0SS
42			q2\0RS		q4B0SS
Чз	q300RR			q3l\RR	q4B0SS	q4B\SS
*Я4

Рис. 11.7. Функция переходов рандомизированной машины Тьюринга

Опишем вкратце поведение М при входной цепочке vv, состоящей из символов 0 и 1. В начальном состоянии q₀ машина М обозревает первый случайный бит и в зависимости от его значения (0 или 1) выполняет одну из двух проверок, связанных с w.

Если случайный бит равен 0, то М проверяет, состоит ли w только из символов 0 или только из символов 1. В этом случае М больше не смотрит на случайные биты и оставля­ет вторую ленту без изменений. Если первый бит w равен 0, то М переходит в состояние qi. В этом состоянии она движется вправо через нули, но останавливается, не допуская, если видит 1. Если в этом состоянии она достигает пробела на входной ленте, то перехо­дит в допускающее состояние q₄. Аналогично, если первый бит w равен 1, и первый слу­чайный бит равен 0, то М переходит в состояние q₂, в нем она проверяет, что все биты w равны 1, и допускает, если это так.

Теперь рассмотрим, что делает М, если первый случайный бит равен 1. Она сравни­вает w со вторым и последующими случайными битами, допуская только тогда, когда они совпадают с первым и последующими битами w, соответственно. Таким образом, в состоянии q₀, обозревая 1 на второй ленте, М переходит в состояние q₃. Отметим, что при этом она сдвигает вправо головку на случайной ленте, оставляя на месте головку на входной. Далее в состоянии q_} она проверяет совпадение содержимого двух лент, сдви­гая обе головки вправо. Если в некоторой позиции она находит несовпадение, то оста­навливается без допускания, а если достигает пробела на входной ленте, то допускает.

Вычислим вероятность допускания определенных входов. Сначала рассмотрим одно­родный вход, в котором встречается только один символ, например, О¹, где / > 1. С веро­ятностью 1/2 первый случайный бит равен 0, и если так, то дальнейшая проверка одно­родности будет успешной, и 0′ допускается. Однако с той же вероятностью 1/2 первый бит равен 1. В этом случае 0′ допускается тогда и только тогда, когда все случайные би­ты со второго по (п + 1)-й равны 0. Это возможно с вероятностью 2~\ Итак, общая веро­ятность допускания 0′ равна

— + -2^ + . 2 2 2

Теперь рассмотрим вариант неоднородного входа w, содержащего как нули, так и единицы, например 00101. Этот вход не допускается, если первый случайный бит равен

• Если же первый бит равен 1, то вероятность допускания составляет 2~’, где /’— длина входа. Таким образом, общая вероятность допускания неоднородной цепочки длиной i равна 2~^(,+|). Например, вероятность допускания 00101 — 1/64. □

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

11.4.4. Класс 1ZV

Язык L класса 7ZV («random polynomial» — случайные полиномиальные) допускается рандомизированной МТ М в следующем смысле.

• Если w не принадлежит L, то вероятность того, что М допускает w, равна 0.
• Если w принадлежит L, то вероятность того, что М допускает w, не меньше 1/2.
• Существует полином р(п), для которого, если w имеет длину п, то все вычисления М, не­зависимо от содержимого случайной ленты, останавливаются после не более р(п) шагов.

Заметим, что определение класса 1ZV использует два не связанных между собой свойства. Пункты I и 2 определяют рандомизированную МТ специального вида, кото­рую иногда называют алгоритмом типа Монте-Карло. Таким образом, независимо от времени работы говорят, что рандомизированная МТ является машиной «типа Монте- Карло», если она допускает или с вероятностью 0, или с вероятностью больше 1/2, ниче­го не допуская с вероятностями между 0 и 1/2. В пункте 3 упоминается время работы, не зависящее от того, является ли МТ машиной типа Монте-Карло.

Пример 11.14. Рассмотрим рандомизированную МТ из примера 11.13. Она удовле­творяет условию 3, поскольку время ее работы есть 0(п) независимо от содержимого случайной ленты. Однако она вообще не допускает никакого языка в смысле определе­ния TLV. Причина в том, что, хотя однородные цепочки вроде 000 допускаются с вероят­ностью не меньше 1/2 и, таким образом, удовлетворяют условию 2, есть другие цепочки, вроде 001, допускаемые с вероятностью, не равной 0 и меньшей, чем 1/2 (цепочка 001 допускается с вероятностью 1/16). □

Пример 11.15. Неформально опишем рандомизированную МТ, которая одновремен­но полиномиальна по времени и является машиной типа Монте-Карло и, следовательно, допускает язык из 1ZV. Ее вход интерпретируется как граф, и вопрос состоит в том, есть ли в этом графе треугольник, т.е. три узла, попарно соединенных ребрами. Входы с тре­угольниками принадлежат языку, остальные — нет.

Алгоритм Монте-Карло циклически выбирает ребро (х, у) и вершину z, отличную от х и у, случайным образом. Каждый выбор определяется просмотром нескольких новых случайных битов на случайной ленте. Для каждой тройки выбранных х, у и z МТ прове­ряет, содержит ли вход ребра (х, z) и (у, z), и, если так, объявляет, что вход содержит тре­угольник.

Всего производится к выборов ребра и вершины; МТ допускает, если любой из них дает треугольник, а если нет, не допускает. Если у графа нет треугольника, то ни один из к выборов не может показать его наличие, что соответствует условию 1 в определении TZV— если вход не принадлежит языку, то вероятность его допускания равна 0.

равна

Предположим, что граф имеет п узлов и т ребер. Если граф имеет хотя бы один тре­угольник, то вероятность того, что три его узла будут выбраны в одном эксперименте,

ЗУ 1 ^Л

, т.е. три из т ребер находятся в треугольнике, и если любое из них

к^тк^п~²;

выбрано, то вероятность того, что выбирается также и третий узел, равна 1 !(п — 2). Эта вероятность мала, но эксперимент повторяется к раз. Поэтому вероятность того, что ни один из к экспериментов не даст треугольника, равна

1-

ч*                                                                   (11.4)

1—

т(п — 2)

Для величины (1 -xf при малых х часто используется приближение в виде е^_кх, где е = 2.718… — основание натуральных логарифмов. Если выбрать к так, что, например кх = 1, то е’^кх будет заметно меньше 1/2 и 1 — е ^кх будет значительно больше 1/2 (около 0.63). Таким образом, можно выбрать к = т(п- 2)/3, чтобы гарантировать, что вероят­ность допускания графа с треугольником, описанная формулой (11.4), не меньше 1/2. Итак, описанный алгоритм является алгоритмом типа Монте-Карло.

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

Приходим к выводу, что язык графов с треугольниками принадлежит классу 1ZT. От­метим, что он также находится в V, поскольку можно провести систематический поли­номиальный поиск всех треугольников. Однако, как упоминалось в начале раздела 11.4, найти примеры языков, которые оказались бы в 1ZV-V, в действительности трудно. □

Распознавание языков из 7?/Р

Предположим, что для распознавания языка L у нас есть полиномиальная по времени машина Тьюринга М типа Монте-Карло. Нам дается цепочка w, и нужно узнать, принад­лежит ли w языку L. Запуская М на w и используя бросание монеты или какое-либо дру­гое устройство генерации случайных чисел для имитации создания случайных битов, по­лучаем следующее.

Если w не принадлежит L, то запуск наверняка не завершится допусканием w.

Если w принадлежит L, то существует не менее 50% шансов, что w будет допущено.

Однако если мы просто возьмем выход данного запуска в качестве определяющего,

то w может оказаться отвергнутым, хотя должно быть допущено (ложный негативный исход, ложный пропуск), но мы никогда не допустим его, если не должны (ложный по­зитивный исход, ложное допускание). Таким образом, следует отличать рандомизиро­ванную МТ от алгоритма, используемого для решения, находится ли w в L. В целом из­бежать ложных негативных исходов невозможно, хотя путем многократного повторения проверки вероятность ложного пропуска можно сделать как угодно малой.

Например, если нужно сделать вероятность ложного пропуска не больше одной билли- онной, можно запустить проверку тридцать раз. Если w принадлежит L, то шансы на то, что все тридцать проверок пропустят допускание, не больше 2 ³⁰, что меньше 10~⁹, или одной биллионной. Вообще, если нам нужна вероятность ложного пропуска меньше, чем с > О, мы должны запустить проверку log₂(l/c) раз. Это количество является константой, если с — константа, а один запуск рандомизированной МТ М требует полиномиального времени, так как предполагается, что L принадлежит TZV. Отсюда повторение проверки также требует по­линомиального времени. Вывод из этих рассуждений формулируется в следующей теореме.

Теорема 11.16. Если L принадлежит 7ZV, то для любой как угодно малой константы с > 0 существует полиномиальный по времени рандомизированный алгоритм, решаю­щий, принадлежит ли w языку L, который не совершает ложных допусканий, а ложные пропуски делает с вероятностью не больше с. □

Класс ZW

Второй класс языков, использующих рандомизацию, называется безошибочным веро­ятностным полиномиальным (zero-error, probabilistic, polynomial), или ZVV. Класс ос­нован на рандомизированной МТ, которая всегда останавливается и имеет ожидаемое время останова, полиномиальное относительно длины входа. Эта МТ допускает свой вход, если попадает в допускающее состояние (и при этом останавливается), и отвергает его, останавливаясь без допускания. Таким образом, определение класса ZW почти совпадает с определением класса V, за исключением того, что ZW разрешает машине вести себя случайным образом, и ограничивается не время работы в худшем случае, а ожидаемое время работы.

МТ, которая всегда дает правильный ответ, но время работы которой зависит от зна­чений некоторых случайных битов, иногда называется машиной Тьюринга типа Лас- Вегас, или алгоритмом типа Лас-Вегас. Таким образом, класс ZW можно считать клас­сом языков, допускаемых машинами Тьюринга типа Лас-Вегас с полиномиально ограни­ченным ожидаемым временем работы.

Является ли дробь 1/2 особенной в определении TVP1

Хотя в определении 1ZP требовалось, чтобы вероятность допускания цепочки w из L была не меньше 1/2, можно определить класс 1ZV с любой другой константой между О и 1 вместо 1/2. Теорема 11.16 говорит, что мы могли бы, повторяя эксперимент, со­вершаемый М, подходящее число раз, сделать вероятность допускания сколь угодно большой, но строго меньшей 1. Кроме того, такая же техника уменьшения вероятно­сти пропуска цепочки из L, использованная в разделе 11.4.5, позволит нам брать ран­домизированную МТ с любой вероятностью допускания цепочки w из L, превышаю­щей 0, и увеличивать эту вероятность до 1/2 путем повторения экспериментов неко­торое постоянное число раз.

В определении 1ZV мы продолжим требовать 1/2 в качестве вероятности допускания, но осознавая, что для определения 1ZV достаточно любой ненулевой вероятности. С другой стороны, изменение константы 1/2 изменит язык, определяемый конкретной рандомизированной МТ. Так, из примера 11.14 следует, что снижение требуемой ве­роятности до 1/16 приведет к тому, что цепочка 001 окажется в языке рандомизиро­ванной МТ, описанной там.

11.4.7. Соотношение между 1ZV и ZW

Между двумя определенными выше рандомизированными классами есть простое со­отношение. Для того чтобы сформулировать теорему о нем, нужно сначала рассмотреть дополнения этих классов. Очевидно, если L принадлежит ZW, то L тоже принадлежит ZW. Причина в. том, что если L допускается МТ М типа Лас-Вегас с полиномиально ог­раниченным ожидаемым временем, то L допускается модификацией М, в которой до­пускание превращено в останов без допускания, и наоборот.

Однако замкнутость 1ZV относительно дополнения не очевидна, поскольку определе­ние машины типа Монте-Карло трактует допускание и отвергание несимметрично. Та­ким образом, определим класс со-1ZV как множество языков L, для которых L принад­лежит TZV, т.е. этот класс образован дополнениями языков из 1ZV.

Теорема 11.17. ZW = 1ZV П zo-TLV.

Доказательство. Сначала покажем, что 1ZV П со-1ZV с ZW. Пусть L принадлежит 7ZV Г) со-7ZV, т.е. как L, так и L имеют МТ типа Монте-Карло с полиномиально ограни­ченным временем. Предположим, что р(п) — достаточно большой полином, ограничи­вающий время работы обеих машин. Построим для L машину Тьюринга М типа Лас- Вегас следующим образом.

Запустим машину типа Монте-Карло для L; если она допускает, М допускает и оста­навливается.

Если машина для L не допускает, запустим МТ типа Монте-Карло для L . Если эта МТ допускает, М останавливается без допускания. В противном случае возвращаемся к п. 1.

Очевидно, М только допускает вход w, если w принадлежит L, и только отвергает w, ес­ли w не находится в L. Ожидаемое время работы в одном цикле (п. 1 и 2) — 2р(п). Вероят­ность того, что один цикл разрешит вопрос, не меньше 1/2. Если w принадлежит L, то п. 1 имеет 50% шансов привести М к допусканию, а если не принадлежит — п. 2 имеет 50% шансов привести М к отверганию. Таким образом, ожидаемое время работы М не больше

2р(п) + 1 2р(п) +12р(п) + \ 2р(п) + …= 4р(п).

2. 4 о

Рассмотрим обратное утверждение. Предположим, что L принадлежит ZW, и покажем, что L находится как в 1ZT, так и в co-TZV. Нам известно, что L допускается МТ М_: типа Лас-Вегас, ожидаемое время работы которой — некоторый полином р(п). Построим для L МТ М₂ типа Монте-Карло следующим образом. М₂ имитирует 2р(п) шагов работы М,. Если Mj допускает в течение этого времени, то же делает и М₂; в противном случае она отвергает.

Предположим, что вход w длиной п не принадлежит L. Тогда М; наверняка не допус­кает w; то же сделает и М₂. Пусть вход w принадлежит L. М\ наверняка в конце концов допускает vv, но это может произойти как в пределах 2р(п) шагов, так и за их пределами.

Однако мы утверждаем, что вероятность того, что М/ допускает w в пределах 2р(п) шагов, не меньше 1/2. Предположим, что эта вероятность является константой с< 1/2. Тогда ожидаемое время работы М) со входом w не меньше (1 — с)2р(п), поскольку 1 — с является вероятностью того, что Mi нужно больше, чем 2р(п) времени. Но если с< 1/2, то 2(1 — с) > 1, и ожидаемое время работы Mj со входом w больше р(п). Получено проти­воречие с предположением, что М) имеет ожидаемое время работы не больше р(п). Это позволяет сделать вывод, что вероятность того, что М₂ допускает, не меньше 1/2. Итак, М₂ является МТ типа Монте-Карло с полиномиально ограниченным временем, что дока­зывает принадлежность L классу 1ZV.

Для доказательства, что L также находится в co-TZT, используется, по существу, та­кая же конструкция, но с отрицанием выхода М₂, т.е. для того, чтобы допустить L , М₂ допускает, когда Mi отвергает в пределах времени 2р(п); в противном случае М₂ отвер­гает. Теперь М₂ является МТ типа Монте-Карло с полиномиально ограниченным вре­менем для L . □

11.4.8. Соотношения с классами V и MV

Из теоремы 11.17 следует, что ZW с 1ZT. Место этих классов между Т и NT опре­деляют следующие простые теоремы.

Теорема 11.18. V С ZW.

Доказательство. Любая детерминированная полиномиально ограниченная МТ явля­ется также полиномиально ограниченной МТ типа Лас-Вегас, не использующей возмож­ности случайных выборов. □

Теорема 11.19. TZTaNP.

Доказательство. Пусть для языка L дана полиномиально ограниченная МТ Mi типа Монте-Карло. Можно построить недетерминированную МТ Мдля L с тем же ограниче­нием времени. Когда Mi рассматривает случайный бит в первый раз, М₂ недетерминиро­ванно выбирает оба возможных значения этого бита и записывает их на свою собствен­ную ленту, имитирующую случайную ленту М]. М₂ допускает, когда допускает М_1г и не допускает в противном случае.

Пусть w принадлежит L. Тогда, поскольку Мj имеет вероятность допускания w не ме­нее 50%, должна существовать последовательность битов на ее случайной ленте, веду­щая к допусканию w. М₂ выберет эту последовательность битов среди прочих, и также допустит. Таким образом, w принадлежит Ь(М₂). Однако если w не принадлежит L, то ни одна последовательность случайных битов не приводит Mj к допусканию, следовательно, нет и последовательности случайных выборов, приводящей к допусканию М₂. Таким об­разом, w не принадлежит Ь(М₂). □

На рис. 11.8 представлены соотношения между введенными здесь и другими «близлежащими» классами.

11.5. Сложность проверки простоты

В данном разделе представлена проблема проверки, является ли целое число про­стым. Вначале обсуждается, почему простые числа и проверка простоты составляют не­отъемлемую часть в системах компьютерной безопасности. Далее показывается, что проблема простоты принадлежит как NT, так и co-NT. Наконец, обсуждается рандоми­зированный алгоритм, показывающий, что эта проблема принадлежит также 7ZT-

11.5.1. Важность проверки пустоты

Целое число р называется простым, если его целыми положительными делителями являются только 1 и само р. Если целое число не является простым, оно называется со­ставным. Каждое составное число можно записать в виде произведения простых един­ственным образом с точностью до порядка сомножителей.

Пример 11.20. Первые пять простых чисел— это 2, 3, 5, 7, 11 и 17. Число 504 со­ставное, а его разложение на простые имеет вид 2^[8] х З² х 7. □

Существует множество способов, повышающих степень компьютерной безопасности и основанных на предположении, что разложение чисел, т.е. поиск их простых делите­лей, является трудной задачей. В частности, схемы, основанные на так называемых RSA- шифрах (R. Rivest, A. Shamir, L. Adleman — изобретатели этих шифров), используют 128-битовые целые, представляющие собой произведения двух простых, занимающих примерно по 64 бит.⁸ Рассмотрим два сценария событий, в которых простые числа игра­ют важную роль.

Шифрование с открытыми ключами

Вы хотите купить книгу у продавца, подключенного к сети. Продавец запрашивает номер вашей кредитной карточки, но печатать номер в форме и посылать форму по те­лефонным линиям или через Internet слишком рискованно, так как некий злоумышлен­ник может подслушать линию или перехватить пакеты, идущие через Internet.

Чтобы предотвратить возможность прочитать номер вашей карточки, продавец посы­лает на ваш броузер ключ, возможно, 128-битовое произведение двух простых чисел, ко­торые компьютер продавца сгенерировал специально для этого. Ваш броузер использует функцию у =Мх), которая берет ключ к и данные х, предназначенные для шифрования. Функцию/ представляющую собой часть схемы RSA, могут знать даже потенциальные злоумышленники, но считается, что без знания разложения к обратную функцию /Г¹, для которой х = fk~^l(y), невозможно вычислить за время, которое меньше экспоненциального по длине к.

Таким образом, даже если злоумышленник видит у и знает, как работает/ он не смо­жет восстановить х (в данном случае номер кредитной карточки), не зная, как к раскла­дывается на множители. С другой стороны, продавец, зная разложение к, сгенерирован­ное им изначально, может легко применить ff^l и восстановить х по у.

Электронная подпись на основе публичных ключей

Исходный сценарий, для которого были построены шифры RSA, был следующим. Вам хотелось бы «подписывать» электронную почту так, чтобы другие могли легко оп­ределить, что эта почта пришла именно от вас, и чтобы никто не мог подделать ваше имя на ней. Например, вам хотелось бы подписать сообщение х = «Я обещаю заплатить Сал­ли Ли 10 долларов», но вы не хотите, чтобы без вашего ведома Салли или кто-то третий могли создать сообщение, якобы подписанное вами.

Для достижения этих целей вы выбираете ключ к, простые сомножители которого из­вестны только вам. Затем публикуете к, например, на Web-странице, так что любой может применить к вашему сообщению функцию /. Если вы хотите подписать упомянутое сооб­щение х и послать его Салли, вы вычисляете у = /Г'(х) ^и посылаете у Салли. Салли может взять к, ваш публичный ключ, с вашей Web-страницы и с его помощью вычислить х = /(у). Таким образом, она знает, что вы действительно пообещали заплатить ей 10 долларов.

Если вы отказываетесь от факта отправки сообщения у, Салли может обосновать в суде, что только вам известна функция и для нее или еще кого-то узнать эту функ­цию было бы «невозможно». Таким образом, только вы могли создать у. Данная система основана на вероятном, но не доказанном предположении, что произведение двух про­стых чисел очень трудно разложить на множители.

Требования к сложности проверки простоты

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

Построение публичных ключей требует быстрого нахождения больших простых чи­сел. Одно из основных положений теории чисел состоит в том, что вероятность п- битового числа быть простым составляет порядка 1 /и. Таким образом, если бы у нас был полиномиальный по времени (относительно п, а не самого числа) способ про­верки, является ли «-битовое число простым, мы могли бы выбирать числа случайно, проверять их и останавливаться, обнаружив простое число. Это давало бы нам поли­номиальный алгоритм типа Лас-Вегас для обнаружения простых чисел, поскольку ожидаемое количество чисел, которые нужно проверить до появления и-битового простого, приблизительно равно п. Например, если нам нужны 64-битовые простые числа, достаточно проверить в среднем около 64 чисел, хотя в наихудшем случае понадобилось бы бесконечно много проверок. К сожалению, похоже, что гарантиро­ванно полиномиальной проверки простоты не может быть, хотя и существует поли­номиальный алгоритм типа Монте-Карло, как будет показано в разделе 11.5.4.

Безопасность шифрования, основанного на RSA-схеме, зависит от невозможности разложить произвольное целое число за полиномиальное (относительно числа битов в ключе) время, и в частности, от невозможности разложить целое, о котором из­вестно, что оно — произведение двух больших простых чисел. Мы были бы счаст­ливы показать, что множество простых чисел образует NP-полный язык, или даже что множество составных NP-полно. Тогда полиномиальный алгоритм разложения доказывал бы, что V = MP, поскольку приводил бы к полиномиальным по времени проверкам для обоих указанных языков. Увы, в разделе 11.5.5 будет показано, что языки как простых, так и составных чисел принадлежат MP. Они дополняют друг друга, поэтому, если бы какой-либо из них был NP-полным, то выполнялось бы ра­венство MP = со-МР, а его правильность весьма сомнительна. Кроме того, принад­лежность множества простых чисел классу 7ZV означает, что, если бы можно было показать NP-полноту этого множества, то верным было бы равенство 1ZV = MP, ко­торое также маловероятно.

11.5.2. Введение в модулярную арифметику

Перед тем как рассматривать алгоритмы распознавания множества простых чисел, представим основные понятия, связанные с модулярной арифметикой, т.е. обычными арифметическими операциями, которые выполняются по модулю некоторого целого числа, зачастую простого. Пусть р — произвольное (положительное) целое число. Тогда целыми по модулюр являются числа 0, 1, …,р- 1.

Сложение и умножение по модулю р (modulo р) определяются в применении к этому множеству из р чисел, когда выполняются обычные действия, после чего берется остаток от деления на р. Сложение совсем просто, поскольку сумма или меньше р, и дополни­тельные действия не нужны, или находится между р и 2р — 2, и тогда вычитание р дает результат в пределах от 0 до р — 2. Модулярное сложение подчиняется об: чным алгеб­раическим законам; оно коммутативно, ассоциативно и имеет 0 в качестве единицы. Вы­читание остается обращением сложения, и модулярную разность х -у можно вычислить путем обычного вычитания и прибавления р, если результат меньше 0. Обратным к х яв­ляется —х, т.е. 0-х, как и в обычной арифметике. Таким образом, -0 = 0, а если х Ф 0, то -х — это то же, что р — х.

Пример 11.21. Пусть р = 13. Тогда 3 + 5 = 8, а7 + 10 = 4, поскольку в обычной ариф­метике 7+10= 17, что не меньше 13. Отнимая 13, получаем правильное значение 4. Значением -5 modulo 13 будет 13-5, или 8. Разность 11-4 modulo 13 равна 7, тогда как 4-11 — 6 (4 — 11 = -7, поэтому нужно прибавить 13 и получить 6). □

Умножение по модулю р выполняется путем умножения обычных чисел и вычисле­ния остатка от деления на р. Умножение также удовлетворяет обычным алгебраическим законам; оно коммутативно и ассоциативно, единицей является I, а нулем (аннигиля­тором) — 0. Оно также дистрибутивно относительно сложения. Однако деление на нену­левые элементы сложнее, и даже существование обратных к целым по модулю р зависит от того, является ли р простым. В любом случае, если х есть одно из целых по модулю р, т.е. 0<х<р, то х~\ или 1/х— это такое число у (если существует), для которого ху — 1 modulo р.

Пример 11.22. На рис. 11.9 показана таблица умножения для ненулевых целых чисел по модулю простого числа 7. Элемент в строке i и столбце j равен произведению ij modulo 7. Отметим, что каждый ненулевой элемент имеет обратный; взаимно обратны 2 и 4, 3 и 5, а I и 6 обратны сами себе, т.е. 2×4, 3×5, 1×1 ибхб равны 1. Таким обра­зом, можно делить на любой ненулевой элемент у, вычислив уи умножив на у~^х. На­пример, 3/4 = 3×4 = 3×2 = 6.

1	2	3	4	5	6
2	4	6	1	3	5
3	6	2	5	1	4
4	1	5	2	6	3
5	3	1	6	4	2
6	5	4	3	2	1

Рис. 11.9. Умножение по модулю 7

Сравним эту ситуацию с таблицей умножения по модулю 6. Во-первых, заметим, что обратные есть только у 3 и 5 (они обратны самим себе). Другие числа обратных не име­ют. Во-вторых, в таблице есть ненулевые элементы, произведение которых равно 0, на­пример, 2 и 3. Такое невозможно в обычной арифметике или в арифметике по модулю простого числа. □

1	2	3	4	5
2	4	0	2	4
3	0	3	0	3
4	2	0	4	2
5	4	3	2	1

Рис. 11.10. Умножение по модулю 6

Есть еще одно различие между умножением по модулю простого числа и по модулю составного, которое оказывается очень важным для проверки простоты. Порядок числа а по модулю р — это наименьшая положительная степень а, равная 1. Приведем без дока­зательства некоторые полезные сведения, связанные с порядком.

Если р — простое, то = 1 modulo р. Это утверждение называется теоремой Ферма.^[9]

Порядок а по модулю простого р всегда является делителем р— 1.

Если р — простое, то существует а, имеющее порядок р — 1 modulo р.

Пример 11.23. Вернемся к таблице умножения по модулю 7 (см. рис. 11.9). Число 2 имеет порядок 3, поскольку 2² = 4 и 2³ = 1. Порядком 3 является 6, так как З² = 2, З³ = 6, З⁴ = 4, З⁵ = 5 и З⁶ = 1. Аналогично находим, что 4 имеет порядок 3,6 — 2, а 1 — I. □

11.5.3. Сложность вычислений в модулярной арифметике

Перед тем как рассматривать применение модулярной арифметики к проверке про­стоты, нужно установить основные факты, связанные со временем выполнения сущест­венных операций. Предположим, нам нужно вычислять по модулю некоторого простого р, и двоичное представление р занимает п битов, т.е. само р близко к 2″. Как всегда, вре­мя выполнения выражается в терминах п, длины входа, а не его «значения» р. Например, счет до р занимает время 0(2″), так что любое вычисление, включающее р шагов, будет не полиномиальным по времени (как функции от и).

На обычном компьютере или на многоленточной МТ можно сложить два числа по модулю р за время О(п). Напомним, что нужно просто сложить два двоичных числа и, если результат не меньше р, вычесть р. Аналогично, на компьютере или на машине Тью­ринга можно умножить два числа за время 0(п²). После обычного умножения и получе­ния результата длиной не более 2п бит, нужно поделить на/? и взять остаток.

Возведение числа х в степень сложнее, поскольку степень сама может быть экспо­ненциальной относительно п. Как мы увидим, большое значение будет иметь возведение х в степень р — 1. Поскольку р близко к 2″, умножение х самого на себя р — 2 раз потребо­вало бы 0(2″) умножений, и даже если бы каждое умножение касалось лишь «-битовых чисел и выполнялось за время 0(п²), общее время было бы 0(п²2″), что не является по­линомиальным относительно п.

К счастью, существует следующий прием «рекурсивного удвоения», который по­зволяет вычислить (или любую другую степень до р) за время, полиномиальное относительно п.

Вычислим не более п степеней х, х², х⁴, х⁸, …, пока степень не превыситр— 1. Каж­дое значение является «-битовым числом, которое находится за время 0(п²) путем возведения в квадрат предыдущего элемента последовательности, поэтому общее время равно 0(и³).

Найдем двоичное представление/; — 1, скажем, р — 1 = a_{n !}…ciia_n. Можно записать

р- 1 =а₀ + 2а, +4а₂+ … + 2^п~’а„_/, где каждое а, есть либо 0, либо 1. Следовательно,

д.р-1 = _jc«₀+2a,+4a₂+—+2″⁴a„_|

что представляет собой произведение тех степеней х²¹, для которых a, = 1. Поскольку все эти степени вычислены в п. 1 и являются «-битовыми, их произведение (или произведение части из них) можно вычислить за время 0(п^ъ). Таким образом, все вычисление х^{р 1} занимает время ()(п^г).

11.5.4. Рандомизированная полиномиальная проверка простоты

Теперь обсудим, как применить рандомизированные вычисления для поиска больших простых чисел. Точнее, покажем, что язык составных чисел принадлежит 1ZV. Метод, который в действительности используется для генерации «-битовых простых чисел, со­стоит в том, что случайно выбирается «-битовое число и много раз, скажем, 50, применя­ется алгоритм типа Монте-Карло для распознавания составных чисел. Если некоторая проверка показывает, что число составное, то оно точно не простое. Если все 50 прове­рок не могут сказать, что оно составное, то вероятность того, что оно действительно со­ставное, не больше 2 ⁵⁰. Таким образом, можно довольно уверенно сказать, что число простое, и этим обосновать безопасность наших операций.

Полный алгоритм здесь не приводится, но обсуждается идея, имеющая очень мало исключений. Напомним, что теорема Ферма гласит: если р — простое, то modulo р для любого х равно I. Верно и то, что если р— составное, и существует х, для которого х^ modulo р. не равно 1, то не менее половины чисел у от 1 до р — 1 имеют У ¹ * 1.

Таким образом, используем следующий алгоритм типа Монте-Карло для составных чисел.

1. Выберем случайно х из диапазона от 1 до р — 1.

Вычислим х^{р 1} modulo p. Заметим, что если р есть «-битовое число, то это вычисле­ние занимает время 0(н³) (см. конец раздела 11.5.3).

Если х^¹ ф 1 modulo р, то допустим вход, т.е. х — составное. В противном случае ос­тановимся без допускания.

Если р является простым, то х¹*»¹ = 1, так что мы всегда останавливаемся без допуска­ния; это одна часть условий типа Монте-Карло — если вход не принадлежит языку, то никогда не допускается. Почти для всех составных чисел не менее половины х будут иметь х¹^¹ ф 1, поэтому у нас есть не менее 50% шансов допускания при любом запуске этого алгоритма, т.е. верно другое условие, налагаемое на алгоритмы типа Монте-Карло.

Представленные рассуждения были бы демонстрацией того, что проблема составных чисел принадлежит 1ZV, если бы не существование небольшого количества составных чисел с, дающих x°~^l = 1 modulo с для большинства х от 1 до с — 1, в частности, для х, взаимно простых с с. Эти числа, называемые числами Кармайкла (Carmichael), требуют проведения еще одной, более сложной, проверки (она здесь не описывается), чтобы убе­диться, что они составные. Наименьшим числом Кармайкла является 561, т.е. можно по­казать, что х^5б0= 1 modulo 561 для всех х, которые не делятся на 3, 11 или 17, хотя 561=3x11x17, очевидно, составное. Итак, утверждается, но без полного доказательст­ва, следующее.

Теорема 11.24. Множество составных чисел принадлежит 7ZV. □

Можно ли разложить на множители за случайное полиномиальное время?

Отметим, что алгоритм из раздела 11.5.4 может сказать, что число является состав­ным, но не говорит, как составное число разложить на множители. Есть основания полагать, что не существует способа разложения, даже с использованием рандоми­зации, которому было бы достаточно полиномиального или хотя бы ожидаемого полиномиального времени. Если бы это предположение было неправильным, то приложения, описанные в разделе 11.5.1, были бы небезопасными и их нельзя было использовать.

11.5.5. Недетерминированные проверки простоты

Здесь обсуждается еще один важный и интересный результат, связанный с проверкой простоты, — язык простых чисел находится в MP П со-МР. Следовательно, язык состав­ных чисел, представляющий собой дополнение языка простых, также принадлежит MP П со-МР. Отсюда следует, что вероятность NP-полноты языков простых и составных чисел ничтожна, поскольку, если бы это было так, истинным стало бы совершенно неве­роятное равенство MP = со-МР.

Одна часть указанного утверждения проста— язык составных чисел принадлежит MV, поэтому язык простых чисел находится в co-MV. Докажем это утверждение.

Теорема 11.25. Множество составных чисел принадлежит MV.

Доказательство. Недетерминированный полиномиальный алгоритм распознавания составных чисел имеет следующий вид.

Имея данное «-битовое число р, угадаем сомножитель/ состоящий не более, чем из п битов (f = 1 или f=p, естественно, не рассматриваются).

Разделим р на/и проверим, что остаток равен 0. Допускаем, если так. Данная часть детерминирована и может быть выполнена за время 0(п²) на многоленточной МТ.

Если р — составное, то оно должно иметь хотя бы один сомножитель/ не равный 1 и р. НМТ, угадывающая все возможные числа, содержащие не более п битов, по одной из ве­ток угадает / Эта ветка ведет к допусканию. Наоборот, допускание НМТ означает, что найден делитель числа р, не равный 1 и р. Таким образом, язык описанной НМТ содер­жит все составные числа, и ничего более. □

Распознавание простых чисел с помощью НМТ сложнее. Можно было угадать при­чину (делитель) того, что число не является простым, но как проверить корректность предположения, что число действительно является простым? Недетерминированный полиномиальный алгоритм основан на том факте (утверждаемом, но не доказанном), что, если р — простое, то существует число х между 1 и р — 1, имеющее порядок р — 1. В частности, в примере 11.23 отмечалось, что при простом р = 7 числа 3 и 5 имеют порядок 6.

Можно легко угадать число х, используя недетерминированность МТ, но совер­шенно неясно, как проверить, что х имеет порядок р — 1. Причина в том, что, если оп­ределение порядка применяется непосредственно, то нужно проверить, что ни одно из чисел х , х³, …, х^{р 2} не равно 1. Но такая проверка требует времени не менее 2″, если р — «-битовое число.

Лучшая стратегия — использовать еще один факт, который утверждался, но не был доказан, а именно: порядок х по модулю простого р является делителем р- 1. Таким об­разом, если бы нам были известны простые делители р — 1^[10], было бы достаточно прове­рить, что х^(р1,/ч Ф 1 для каждого простого сомножителя q числа р- 1. Если бы ни одна из этих степеней х не равнялась 1, то порядком х было бы р — 1. Число таких проверок есть О(п), поэтому все их можно выполнить с помощью полиномиального алгоритма. Конеч­но, разложить р- 1 на простые сомножители нелегко, но можно угадать их, и прове­рить, что

а) их произведение действительно равно р — 1;

б) каждый из них является простым, используя данный недетерминированный полиномиальный алгоритм рекурсивно.

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

Теорема 11.26. Множество простых чисел принадлежит NV.

Доказательство. Пусть р— «-битовое число. Если п не больше 2 (т.е. р— это 1, 2 или 3), то отвечаем сразу: 2 и 3 — простые, 1 — нет. В противном случае выполним следующее.

Угадаем список сомножителей (q_h q₂, …, qi), двоичные представления которых вме­сте занимают не более 2п битов, и ни одно из них не имеет более п — 1 битов. Одно и то же простое число может появляться несколько раз, поскольку р — 1 может иметь сомножитель, возводимый в степень больше 1. Например, если р= 13, то простые сомножители р- 1 = 12 образуют список (2, 2, 3). Данная часть алгоритма недетер- минирована, но каждая ветвь требует времени 0(п).

Перемножим все сомножители q, и проверим, равно ли их произведение р — 1. Эта часть требует времени не более 0(п²) и является детерминированной.

Если произведение сомножителей равно р — 1, то рекурсивно проверим, является ли каждый из них простым, используя данный алгоритм.

Если не все q просты, угадаем значение х и проверим неравенство х^(р1,/ч Ф 1 для ка­ждого из q. Эта проверка обеспечивает, что х имеет порядок р — 1 modulo р, по­скольку, если бы это было не так, то его порядок должен был бы делиться хотя бы на одно из (р — l)/q, но мы только что установили, что он не делится. В подтверждение заметим, что любое х при возведении в степень его порядка должно равняться 1. Возведения в степень можно выполнить эффективным методом, описанным в разде­ле 11.5.3. Таким образом, нужно выполнить не более к возведений в степень, что не больше п, и каждое можно выполнить за время 0(п³), что дает общее время 0(п⁴) для каждого шага.

Наконец, нужно проверить, что приведенный недетерминированный алгоритм поли­номиален. Каждый шаг, за исключением рекурсивного шага 3, требует времени 0(п⁴) вдоль любой недетерминированной ветви. Поскольку рекурсия нелинейна, рекурсивные вызовы можно изобразить в виде дерева (рис. 11.11). В корне находится «-битовое р, проверяемое на простоту. Сыновьями корня являются qj— угадываемые сомножители р — 1, которые также нужно проверить на простоту. Под каждым qj находятся угадывае­мые сомножители qj — 1, которые также нужно проверить, и так далее, пока не дойдем до чисел, состоящих не более, чем из 2 бит — листьев дерева.

Произведение сыновей любого узла меньше значения в самом этом узле, поэтому произведение значений в узлах любого уровня не более р. Время работы, выполняе­мой для узла со значением /’, исключая работу в рекурсивных вызовах, оценивается
как а(log₂/)⁴ для некоторой константы а, поскольку это время прямо пропорцио­нально четвертой степени количества битов, необходимых для двоичного представ­ления значения /’.

я, я 2 …                              ч, /1\ /\ /\

Уровень корня Уровень 1 Уровень 2

Рис. 11.11. Рекурсивные вызовы, совершаемые алгоритмом из теоремы 11.26, образуют дерево высотой и шириной не более п

Таким образом, чтобы получить верхнюю оценку времени работы на любом уровне, ограничим сверху сумму ^ a(log₂(/y))⁴, учитывая, что произведение /_у — — — не превосхо­дит р. Если i) = р, и других ij нет, то сумма равна a(Iog₂р)⁴, т.е. не превосходит an⁴, по­скольку п — число битов двоичного представления р, a log₂р не более п.

Итак, время работы на каждом уровне глубины не превышает 0(п⁴). Так как у дерева не более п уровней, для любой ветви недетерминированной проверки, является ли р про­стым, достаточно 0(п⁵). □

Теперь ясно, что языки и простых, и составных чисел находятся в MP. Если бы один

из них был NP-полным, то по теореме 11.2 это доказывало бы, что MP = со-МР. 11.5.6. Упражнения к разделу 11.5

• Вычислите следующие значения по модулю 13:

а) 11+9;

б)   (*) 9 — 11;

в) 5×8 ;

г)    (*) 5 / 8; Д) 5⁸.

• В разделе 11.5.4 утверждалось, что .г⁵⁶⁰ = 1 modulo 561 для большинства значе­ний х между 1 и 560. Выберите какие-нибудь значения х и проверьте это равен­ство. Конечно, сначала выразите 560 в двоичном виде, а затем