Случайность как вычислительный ресурс

Архив

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

«Дело в том, что самые интересные и изящные научные результаты сплошь и рядом обладают свойством казаться непосвященным заумными и тоскливо-непонятными…»
А. и Б. Стругацкие.
«Понедельник начинается в субботу»

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

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

Во многих случаях сравнительно легко уменьшить вероятность ошибки вероятностного алгоритма. Для этого алгоритм запускается несколько раз и выбирается тот ответ, который встречается чаще всего. Вероятность ошибки будет довольно быстро убывать. Приведем пример. Если вероятность ошибки алгоритма равна 0,4 (многовато, не правда ли?), то при повторении его работы вероятность ошибки будет уменьшаться вдвое примерно за тридцать повторений. Выполнив алгоритм тысячу раз, мы достигнем вероятности ошибки 10^-9; две тысячи повторений дадут 10^-18, что более чем достаточно с практической точки зрения. Такая процедура называется усилителем вероятности.

Как появились вероятностные алгоритмы

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

Пока алгоритмы использовались в основаниях математики, ничего иного и не требовалось. Имея строгое определение алгоритма, математики получили возможность отвечать на вопрос: существует ли для данной задачи алгоритм ее решения? Почти во всех практически интересных случаях на этот вопрос удается ответить.

Появление компьютеров привело к постановке новых вопросов. Оказалось, что есть алгоритмические задачи, непосильные для компьютеров ¹. Дело в том, что некоторые алгоритмы работают очень медленно. Возьмем хрестоматийный пример. Хорошо известно ², что существует алгоритм решения любых задач элементарной геометрии. Подавая на вход такого алгоритма описание геометрической задачи, на выходе получим ее решение. Однако ждать придется долго. Точные оценки времени его работы зависят, конечно, от подробностей реализации, но не будет грубой ошибкой сказать, что универсальный алгоритм решения геометрических задач затратит на решение всех задач из школьного учебника время, заведомо превышающее время существования Вселенной ³.

Эффективными алгоритмами занимается теория сложности вычислений. В ней учитываются ограничения, накладываемые на вычисления в реальном мире. При этом все базируется на простейшей метафоре. Вычислительная машина, как и всякая машина, потребляет некоторый ресурс. А поскольку ресурсы окружающего мира ограничены ⁴, то алгоритмы, требующие их слишком много, реализовать невозможно. Основными вычислительными ресурсами, очевидно, являются время вычисления и требуемая для вычислений память ⁵.

Интересно, что если одновременно используется несколько вычислительных ресурсов, между ними возможен «обмен» (trade-off): скажем, увеличивая память, можно сократить время вычисления.

Случайные биты - и это замечательно! - тоже являются своеобразным вычислительным ресурсом. Вероятностные алгоритмы используют его, чтобы сократить потребление другого ресурса (обычно времени вычисления).

Каким же образом случайность экономит время? Рассмотрим самую общую ситуацию.

Случайный поиск

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

Таким образом, выбор случайного варианта позволяет в некотором ослабленном смысле произвести большой перебор вариантов за небольшое время. Можно с некоторой натяжкой сказать, что вероятностный поиск «распараллеливает» перебор вариантов.

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

Проверка простоты числа

Самый известный и важный с практической точки зрения пример эффективного вероятностного алгоритма - проверка простоты числа. Напомним, что натуральное число называется простым, если оно делится нацело только на единицу и на само себя. Скажем, 3, 5, 7 - числа простые, а 9 - нет. Когда числа маленькие, проверку простоты легко выполнить, проверяя делимость на все числа, меньшие данного ⁶. Но что делать, если нужно проверить, скажем, число 170141183460469231731687?

Тем не менее, ответ можно получить буквально за несколько секунд на персональном компьютере (ввод этого числа с клавиатуры займет больше времени). Число - составное, хотя алгоритм и не говорит ничего о том, каковы его делители (используются косвенные признаки простоты числа).

Алгоритм проверки простоты устроен так, что ответ «число - не простое» он дает с достоверностью (вероятность ошибки 0). А вот если ответ «число - простое», то существует некоторая вероятность ошибки, которую можно сделать достаточно малой, используя описанное выше усиление вероятностей. (Алгоритмы такого типа называются Лас-Вегас-алгоритмами, в противоположность алгоритмам Монте-Карло, допускающими ошибки в обоих вариантах ответа. Такая терминология не подразумевает различия технологий в игорных домах Нового и Старого Света. Она возникла и прижилась случайно.)

Если перебирать числа одно за другим, начиная с приведенного выше, то первым «простым» окажется 29-е по счету число. Почему слово «простым» взято в кавычки? А потому, что утверждать наверняка простоту этого числа автор статьи не берется, поскольку проверка проводилась вероятностным алгоритмом. Можно лишь полагать, что вероятность ошибки мала.

Вероятностные алгоритмы долгое время смущали именно этим странным свойством. Приведенное выше число либо простое, либо нет. Как понимать утверждение, что оно простое с вероятностью ошибки меньше одной стомиллионной? Если бы на простоту этого числа опиралось доказательство какой-то теоремы, следовательно, теорема была бы верна лишь с некоторой вероятностью?!

Делалось множество попыток построить эффективный алгоритм проверки простоты числа. Наилучшее на сегодняшний день достижение выглядит довольно странно: если верна некоторая математическая гипотеза (вариант знаменитой гипотезы Римана о нулях дзета-функции), то эффективный алгоритм проверки простоты существует. Если же эта гипотеза неверна, то ничего пока сказать нельзя. Замечательно, не правда ли?

Совершенные паросочетания

Иногда применение вероятностных алгоритмов дает более скромный выигрыш в скорости, чем в случае проверки простоты числа. В качестве примера приведем задачу о совершенном паросочетании в графе. Сформулировать ее можно так. Пусть в путешествие отправилась группа людей. Известно, кто с кем дружит. Можно ли расселить людей по двухместным каютам так, чтобы в каждой каюте оказались друзья?

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

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

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

Экзотические модели вычислений

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

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

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

Пример 1. Пристрастный советник.

Пусть алгоритм решает некоторую задачу, в которой ответом является «да» или «нет», и имеет возможность консультироваться со всезнающим советником. У советника есть только один недостаток: он преследует свои собственные цели и поэтому необязательно говорит правду. Цель советника в том, чтобы было принято положительное решение. Тогда алгоритм должен быть устроен так, чтобы в случае, когда ответ отрицательный, ответы советника не могли привести к принятию положительного решения.

Оказывается, существуют вероятностные алгоритмы использования такого пристрастного советника, позволяющие со сколь угодно малой вероятностью ошибки решать все задачи, которые можно решить, используя не слишком большую память (без ограничений на время вычисления). Типичным примером подобной задачи является поиск выигрышной стратегии для позиционной игры. Глядя на ситуацию со стороны советника, можно сказать и так: игра против любого противника, использующего сколь угодно сложную стратегию, оказывается не сложнее игры с природой (природа - это противник, стратегия действий которого считается известной, но допускает случайный выбор).

Математика, лежащая в основе этих алгоритмов, не так уж сложна, но непривычна. Например, приходится расширять область логических значений, заменяя 0 и 1 (ложь и истину) на набор остатков по модулю достаточно большого простого числа. Смысл такого действия и сегодня остается непонятым.

Пример 2. PCP-теорема.

Это теорема, доказанная в начале 1990-х годов, произвела настолько сильное впечатление, что о ней писала даже нематематическая пресса (например, газета «New York Times»). В вольном пересказе она формулируется следующим образом: можно придумать такой способ записи математических доказательств, при котором проверять (в вероятностном смысле, то есть с небольшой вероятностью ошибки) правильность доказательства можно, изучив несколько случайно выбранных мест в доказательстве (их число не зависит от длины доказательства!).

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

Сила PCP-теоремы в том, что объем запрашиваемой у суперкомпьютера информации не зависит от объема проделанных им вычислений, а определяется лишь той вероятностью ошибки, которую вы согласны допустить.

Пример 3. Доказательства с нулевым разглашением.

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

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

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

Дополнительные возможности: квантовые вероятности

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

Квантовые алгоритмы напоминают вероятностные. Прежде всего, неопределенностью результата. Когда считывается (физики предпочитают говорить: измеряется) результат работы квантового вычислителя, могут получаться разные значения, вероятности которых определяются законами квантовой механики.

Если использовать в вычислительном устройстве разрозненные квантовые биты, то получающаяся неопределенность ничем не отличается от обычной случайности. Именно такие системы могут служить идеальными датчиками случайных чисел. Реализовать их нетрудно. К примеру, долгоживущий радиоактивный изотоп можно использовать как практически неисчерпаемый источник случайных битов ⁹.

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

Попробуем (крайне грубо) описать один из простейших квантовых алгоритмов - алгоритм Гровера. Он решает универсальную задачу перебора, состоящую в том, что нужно найти ответ на некоторый вопрос, используя «оракул», или «черный ящик» - устройство, которое на предложенный ему вариант ответа сообщает, подходит этот вариант или нет.

Действуя классическим способом, в такой ситуации можно лишь перебирать один за другим возможные варианты ответа. Если использовать случайный выбор, можно сократить перебор примерно вдвое. А применение квантового алгоритма позволяет сократить перебор гораздо сильнее: нужное количество запросов будет пропорционально квадратному корню из числа возможных вариантов. Если вариантов 1000 - квантовому алгоритму потребуется 100 попыток, если вариантов 100 миллионов, то 10000 попыток.

Обратите внимание, что такое сокращение времени работы специалисты по теории сложности считают непринципиальным. Их устраивает только экспоненциальное ускорение перебора. Причина в том, что в практически важных случаях вариантов перебора гораздо больше. Допустим, ответ записывается 64 байтами. Число, о котором шла речь в разделе про проверку простоты, намного меньше, чем количество возможных состояний 64 байт (а значит, вариантов ответа). Корень из этого числа «намного меньше», но все же значительно превосходит количество всех сложений, сделанных на планете Земля в двадцатом веке (как людьми, так и компьютерами).

Как же устроено ускорение перебора в алгоритме Гровера? Для этого сооружается еще один оракул, на этот раз полностью нами контролируемый ¹⁰. Этот вспомогательный оракул считает правильным ответом «равномерную смесь» всех возможных вариантов ответа. То, что мы назвали «равномерной смесью», является особым квантовым состоянием, которое при измерениях действительно будет давать все возможные варианты равновероятно. Но если теперь мы составим сложную систему из исходного и построенного нами оракула и начнем задавать им вопросы попеременно, начиная с правильного ответа на наш вспомогательный вопрос, то спустя некоторое количество вопросов (как уже говорилось, пропорциональное квадратному корню из числа вариантов) измерение зафиксирует со значительной вероятностью правильный ответ на вопрос исходного оракула.

Пояснить это довольно трудно. Разве что можно вспомнить эпизод из известного мультфильма, где почтальон общается через дверь с говорящей птицей, которая повторяет одно и то же: «Кто там?» Почтальон отвечает: «Это я, почтальон Печкин…» И так много-много раз. Заканчивается все тем, что почтальон вопрошает: «Кто там?» и получает в ответ: «Это я, почтальон Печкин».

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

Насколько велики возможности квантовых алгоритмов? Как вы уже догадываетесь, точного ответа на этот вопрос нет. Зато наблюдается удивительная аналогия со случаем вероятностных алгоритмов. Есть небольшое количество примеров, когда достигается принципиальный выигрыш по сравнению с классическими детерминированными алгоритмами: проверка простоты для вероятностных вычислений, факторизация - для квантовых. Есть примеры, когда выигрыш не столь принципиален, но имеются другие преимущества. Для вероятностных алгоритмов это, например, задача о совершенном паросочетании. Для квантовых - универсальная задача перебора. Для более сложных моделей и вероятностные, и квантовые вычисления дают значительные усиления. Скажем, описанный выше вероятностный диалог с советником может быть квантовым образом упакован всего в два раунда.

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

---

1 (обратно к тексту) - Имеется в виду любое вычислительное устройство, реализация которого хотя бы в принципе возможна в физическом мире.
2 (обратно к тексту) - Первым это доказал А. Тарский - один из создателей теории алгоритмов.
3 (обратно к тексту) - Оговорка про универсальность важна: существуют программы, которые во многих случаях за приемлемое время доказывают геометрические теоремы, хотя и не всегда добиваются успеха. Программа такого типа может справиться с задачником по геометрии гораздо быстрее.
4 (обратно к тексту) - Некоторые физики утверждают, что в нашем распоряжении есть всего-навсего 10⁸⁰ элементарных частиц.
5 (обратно к тексту) - По большому счету, это пространство и время.
6 (обратно к тексту) - На самом деле, достаточно проверить только числа, не превосходящие квадратный корень из данного числа.
7 (обратно к тексту) -Ситуация вполне «из жизни». Не правда ли? - Ю.Р.
8 (обратно к тексту) - Ее формулировка звучит так: можно ли перенумеровать вершины двух графов таким образом, чтобы в обоих графах вершины с одинаковыми номерами были либо соединены ребром, либо нет.
9 (обратно к тексту) - Мы опускаем сейчас тонкости, связанные с тем, что закон распределения получающихся битов отличается от равномерного. Скажем лишь, что он нам заранее известен.
10 (обратно к тексту) - В том смысле, что его поведение нам всегда известно. Полностью контролируемый оракул - согласитесь, это так знакомо! - Ю.Р.