По грани вычислимого

Вообще говоря, теоретическую информатику можно считать разделом математики, вот только постановки задач в ней берутся не из физики, как в математическом анализе, и не из экономики, как в теории игр, а из практических или фундаментальных вопросов в программировании, проектировании информационных систем и других сферах, связанных с вычислительными устройствами. Можно сказать, что основным предметом этой области является разграничение между задачами, которые в принципе решаются на компьютере, и теми, чье решение невозможно. В отличие от других разделов математики, здесь очень большая часть результатов носит условный характер: они верны и осмысленны только в случае истинности той или иной недоказанной гипотезы. Из этих гипотез выделим и кратко опишем две важнейшие: неравенство классов P и NP и существование односторонних функций. Они важны для понимания как состояния теории в целом, так и вклада Вигдерсона. P=NP? Проблема равенства P и NP была поставлена ровно полвека назад, в 1971 году, независимо в работах американо-канадского математика Стивена Кука и советского математика Леонида Левина (позднее он также эмигрировал в США из-за политического преследования в СССР). Если говорить кратко, то проблема заключается в оценке алгоритмической сложности переборных задач. Разберемся сначала, о каких задачах идет речь и что такое алгоритмическая сложность. Задачи здесь изучаются массовые, то есть содержащие бесконечное число различных формулировок: решить уравнение ( x 2 + 20x + 21 = 0) — это конкретная задача, а решить уравнение ( x 2 + px + q = 0) для всех p и q — массовая. Кроме того, мы ограничимся дискретными задачами с бинарным ответом. Дискретность означает, что условие записывается конечным числом битов — например, p и q должны быть целыми. Бинарность ответа означает, что ответ будет «да» или «нет»: нужно не найти решение, а указать, есть ли оно. Нас будут интересовать алгоритмические решения, то есть компьютерные программы, которые принимают на вход условие задачи, и, проработав некоторое время, возвращают правильный ответ. Сложность задачи определяется временем работы алгоритма. Поскольку разных условий бесконечно много, смотрят не на конкретные числа, а на порядок роста времени решения в зависимости от размера задачи (в битах). Говорят, что алгоритм полиномиален, если время его работы растет как многочлен, то есть с задачами размера n алгоритм работает не дольше, чем cn d для некоторых констант c и d . На практике редко используют алгоритмы со степенью многочлена больше 3, но в теории полиномиальность считается синонимом вычислительной эффективности. Это может показаться странным: если время растет как n 20 , то работа с задачей из 10 битов потребует мощнейшего суперкомпьютера, а если время растёт как n 100 , то вычисления будут принципиально нереализуемы в силу физических причин . Почему же мы считаем такие алгоритмы эффективными? Во-первых, любая конкретная граница была бы произвольной и зависела бы от особенностей компьютерной архитектуры. Во-вторых, как правило, если какой-то полиномиальный алгоритм для решения задачи мы нашли, то дальше его можно улучшать, чтобы сделать реализуемым на практике. Класс P как раз объединяет все задачи, для которых найдется хоть какой-то полиномиальный алгоритм. Теперь определим, что такое класс NP, или же класс переборных задач. Пусть есть задан некоторый эффективный, то есть полиномиальный алгоритм, проверяющий, является ли данная запись решением данной задачи. Вот примеры: дан граф социальной сети, нужно проверить, верно ли, что в данной группе людей все знакомы друг с другом; дана головоломка судоку, нужно проверить, является ли данное заполнение квадрата ее решением; дано число побольше и число поменьше, нужно проверить, что первое делится на второе; дан список требований, которым должно удовлетворять расписание занятий (например, у одного преподавателя не должно быть двух занятий одновременно или слишком большого числа занятий подряд), нужно проверить их выполнение в данном расписании; даны аминокислотная и пространственная структуры белка, нужно проверить, действительно ли белок так свернется; дана математическая теорема и формальная запись ее доказательства, нужно проверить корректность доказательства. В каждом примере возникает задача о наличии подходящей записи: есть ли решение у головоломки, реализуемы ли требования к расписанию, доказуема ли теорема и так далее. (В случае с теоремой важно, чтобы доказательство было полиномиальной длины). Подобные задачи и образуют класс NP. Их можно придумать огромное количество, и для решения каждой из них возникает переборный алгоритм: рассмотрим все допустимые записи и про каждую из них проверим, является ли она подходящей. В процессе такого перебора либо нужное решение найдется, либо станет ясно, что его не существует. Однако такой перебор будет слишком долгим — экспоненциальным, — и начиная с некоторого размера задачи компьютер с ним никогда не справится — ни существующий, ни любой мыслимый. Вопрос заключается в следующем: есть ли универсальный способ сократить такой огромный перебор до полиномиального, то есть включено ли NP в P? Для некоторых задач сократить перебор можно: например, третий пример из списка выше соответствует известнейшей задаче о проверке числа на простоту (точнее, тут проверка обратная: есть ли у числа делитель, то есть является ли число составным). В 2002 году индийские математики Маниндра Агравал, Нирадж Каял и Нитин Саксена опубликовали алгоритм (ставший известным под названием AKS по первым буквам фамилий авторов), проверяющий простоту за полиномиальное время, и показали, что в этой задаче большой перебор не нужен. Тут стоит отметить, что многочлен измеряется не от самого числа, а от количества знаков в его десятичной записи, то есть от его логарифма. Однако для множества других задач подобных алгоритмов не найдено и есть серьезные основания полагать, что их и нет. В конце концов, это прекрасно согласуется с обычной интуицией: в большинстве жизненных задач найти подходящий вариант куда сложнее, чем оценить предложенный. При этом решения задач об оптимальном расписании или о сворачивании белков могли бы кардинально улучшить повседневную жизнь людей, а решение задачи о поиске доказательств теорем — радикально продвинуть наши знания в математике. Возможность криптографии С другой стороны, P≠NP — необходимое требование для работы почти любых криптографических протоколов. Большинство из них можно взломать, перебрав возможные ключи или пароли, а их надежность строится на том, что такой перебор неосуществим, а более эффективных способов взлома нет. Если же P=NP, то такие способы есть и, вполне возможно, они осуществимы и на практике. Поэтому такое открытие поставило бы под угрозу все современное мироустройство, что обыграно в фильме Travelling Salesman . Однако один только факт, что P≠NP, криптографию не спасет. Когда речь идет о сложности алгоритмических проблем, время работы измеряется в худшем случае: если в каких-то ситуациях алгоритм работает долго, то задача считается сложной. Для криптографии этого недостаточно: алгоритм взлома должен работать долго не время от времени, а всегда или почти всегда. И тут необходимым условием является существование односторонней функции: такой, что по аргументу можно быстро вычислить значение, а вот по значению вычислить хоть какой-то его прообраз почти невозможно. Известным кандидатом на роль такой функции является перемножение чисел: это очень простая операция, а вот разложить число на множители может быть сложно. И AKS-алгоритм тут не поможет: он говорит, есть ли у числа нетривиальные множители, но не помогает их найти. Зато потенциально может помочь квантовый компьютер, для которого есть алгоритм Шора. Однако и квантовые компьютеры не взломают все криптографические протоколы: например, им не поддаются большинство криптографических хеш-функций, а также криптографические протоколы, построенные на задачах из теории решеток. P=BPP? Еще один важнейший вопрос — сила рандомизированных алгоритмов. Это процедуры, использующие в своей работе случайные биты. С одной стороны, в результатах могут возникнуть ошибки. С другой стороны, они могут работать значительно эффективнее детерминированных, а если ошибки маловероятны, то алгоритмы вполне можно использовать. Например, задолго до AKS-алгоритма были известны вероятностные тесты простоты. Они используются и сейчас, так как работают гораздо быстрее изобретения индийских математиков, а вероятность ошибки очень мала. Но есть ряд задач, для которых известны лишь вероятностные полиномиальные алгоритмы, а детерминированные требуют огромного перебора или другой экспоненциально долгой процедуры. Это в принципе невозможно изменить или мы просто пока не придумали подходящий алгоритм? Обычно эту проблему формулируют как вопрос о равенстве P и BPP. Для задач из класса P существуют полиномиальные детерминированные алгоритмы, а для задач из класса BPP — вероятностные. На первый взгляд проблема равенства P и NP и проблема равенства P и BPP очень похожи: и в NP, и в BPP есть задачи, для которых неизвестно полиномиальных алгоритмов. Тем не менее, многие исследователи считают, что ответы разные: P≠NP, но P=BPP. Ниже мы увидим, почему. Я знаю пароль Получив представление о ключевых проблемах теоретической информатики, можно начать знакомство с достижениями Вигдерсона. Среди них наиболее широко известна концепция доказательств с нулевым разглашением (zero-knowledge proofs), разработанная совместно с Одедом Гольдрайхом и Сильвио Микали. Объяснить, что это такое, можно на таком примере. Пусть Боб решает какую-то головоломку, например, судоку, а Алиса знает решение. Боб уже отчаялся и вот-вот бросит поиск, а Алиса хочет его приободрить, убедив, что решение точно есть. Как это сделать, не выдав никакой подсказки? Оказывается, есть универсальная многораундовая процедура: Алиса хитрым образом шифрует решение, а потом по запросу Боба точечно расшифровывает, так что прочитанный фрагмент убеждает Боба, что решение было правильным, но при этом не раскрывает никакой информации о самом решении. Опишем один раунд одной из возможных процедур подробнее. Вначале Алиса шифрует известное ей решение судоку простейшим шифром замены. Будем считать, что она заменяет цифры 1,2,...,9 на буквы A,B,...,I, но выбирает соответствие случайным образом. Но зашифрованное решение целиком предъявлять нельзя, иначе Боб легко восстановит исходное. Поэтому все ячейки закрываются «шторками». А Боб делает одно из следующих действий: открыть все шторки в произвольной строке и убедиться, что каждая буква встречается ровно один раз; открыть произвольный столбец; открыть произвольный квадрат 3×3; открыть поля, на которых изначально стояли цифры. На них проверяется корректность замены: одинаковые цифры должны замениться на одинаковые буквы, а разные на разные. Таким образом, всего есть 28 разных проверок (9 строк, 9 столбцов, 9 квадратов плюс проверка на корректность замены). Если у Алисы есть решение, то она честно проведет все манипуляции и пройдет все проверки. Если решения нет, то где-то должна быть ошибка — и Боб с вероятностью хотя бы 1/28 ее обнаружит. При этом никакой информации про решение Боб не узнает: при первых 27 проверках он увидит только случайную перестановку букв от A до I, а при 28-й — случайную замену исходного условия. Если повторить процедуру достаточно много раз, то сжульничавшей Алисе должно исключительно повезти, чтобы Боб ни разу не наткнулся на ошибку. Если Алиса каждый раз выбирает случайный шифр заново, то Боб все так же не узнает никакой секретной информации. Остается вопрос, как реализовать «закрытие и открытие шторок», если между Алисой и Бобом нет физического контакта. В работе Вигдерсона показано, что это можно сделать на основе любой односторонней функции: требуется специальный протокол «привязки к сообщению». Кроме того, этот алгоритм можно распространить с судоку на любую задачу с быстрой проверкой решения, то есть на весь класс NP. Заметим, что именно для судоку есть более простой физический протокол , основанный на тасовании карт, но его сложнее переделать в криптографический. Какая от этого практическая польза? На основе концепции нулевого разглашения можно построить систему аутентификации, устойчивую к фишингу, краже паролей при помощи поддельных сайтов. Пользователь будет доказывать серверу, что знает подходящий пароль, не раскрывая никакой информации об этом пароле. Взломщик, не знающий пароля, не сможет ничего доказать серверу, а поддельный сервер не сможет ничего узнать о пароле пользователя. На этом строится протокол SRP , он внесен в стандарты, его используют при идентификации ProtonMail, iCloud и некоторые банковские приложения, а появившийся несколько лет назад протокол OPAQUE обещает устранить ряд недостатков SRP. Тем не менее, в большинстве случаев аутентификация работает менее надежными способами, и на короткое время сервер получает пароль в исходном виде. Более широкому распространению протоколов с нулевым разглашением мешает как определенная инерция мышления разработчиков, так и требования обратной совместимости: например, такой сценарий требует нескольких раундов общения и потому его исполнение в существующих браузерах может быть затруднено. Хорошие случайности Пожалуй, наиболее глубок и разносторонен вклад Вигдерсона в теорию вероятностных вычислений. Заметьте, что и одним из ключевых элементов описанной схемы для судоку было случайное шифрование. Именно благодаря нему Боб ничего не узнавал о решении по открытой информации. Но часто рандомизация помогает и решению чисто алгоритмических задач, преобразованию входа в выход. Представьте, что вы попали в центр лабиринта Минотавра. Минотавр пока спит, и точно известно, что выход есть, так что у вас есть время на побег. Проблема в том, что лабиринт очень большой и многоуровневый, все комнаты похожи друг на друга, а никаких средств записи у вас нет. Так что вы не сможете составлять карту по мере обхода лабиринта и не сможете запомнить, какие комнаты уже обошли. Если бы лабиринт был плоским, можно было бы действовать по правилу левой руки: взяться за стену и на всех развилках поворачивать налево — так вы обойдете весь лабиринт и в какой-то момент наткнетесь на выход. Но для сложной пространственной структуры такой метод уже не сработает: никакого естественного порядка обхода ввести не получится. Оказывается, неплохим решением в такой экстремальной ситуации будет случайное блуждание: оказавшись в новой комнате, выбирайте случайно любую из соседних. В среднем вы доберетесь до выхода достаточно быстро, хотя если очень не повезет, то останетесь в лабиринте навсегда. Использование случайности в алгоритмах ставит несколько важных вопросов. Один мы уже упоминали: нельзя ли придумать процедуру для решения той же задачи, но без использования случайных битов? Для задачи о лабиринте Минотавра можно, что доказал один из коллег Виндерсона — Омер Рейнгольд. Но для других, более сложных задач ответ неизвестен. Другой вопрос более практичен: откуда брать случайные биты в достаточном количестве для работы наших алгоритмов и процедур взаимодействия? И насколько повлияет качество случайных битов на точность ответа и надежность протокола? Давайте сначала разберемся с качеством случайности. Ее источники разделяют на два вида: генераторы истинно случайных чисел и генераторы псевдослучайных чисел. Генераторы истинно случайных чисел получают данные из какого-то природного, технического или социального процесса, который протекает случайным образом. Это может быть, например, радиоактивный распад, атмосферные течения, шум аудиокарты, движение мышкой пользователя или котировки на бирже. Есть и специально сконструированные квантовые приборы, в которых стоит лазер, излучающий один фотон, полупроницаемое зеркало и два регистратора, проверяющих, отразился фотон от зеркала или нет. Но какая бы ни была природа процесса, регистрирующий прибор будет неизбежно вносить искажения, так что выдаваемые им биты могут иметь те или иные скошенности или корреляции. В то же время генераторы псевдослучайных чисел на самом деле являются полностью детерминированными процедурами, но их выход «очень похож» на случайный, так что часто используется вместо него. Примером генератора «на коленке» является такой алгоритм: возьмите четырехзначное число, не оканчивающееся на два нуля, возведите его в квадрат и получите число восьмизначное (если получилось меньше знаков, добавьте в начало недостающие нули). Теперь возьмите серединку, то есть число, образованное знаками с 3-го по 6-й. Это будет следующее число, с которым можно проделать ту же процедуру, и дальше она повторяется по циклу. Например, начнем с числа 2021. Возведя в квадрат, получим 04084441. Серединка — 0844. Снова возведя в квадрат, получим 00712336. Серединка — 7123. Дальше получится 7371, 3316, 9958, 1617, 6146, 7733, 7992, 8720 и так далее. Никакой явной закономерности не просматривается, хотя процедура порождения очень простая. Конечно, у процедуры есть недостатки: например, число 3792 неожиданно переходит само в себя. На практике используют более продвинутые генераторы, но, например, для лотерей псевдослучайные числа не подойдут в принципе. Для приложений важно как качество случайных битов, так и их количество. Эти требования противоречат друг другу: при «массовом производстве» битов будет возникать разного рода «брак». Предположим, что у нас есть два источника: один очень хороший, но медленный (например, лотерейный барабан), другой низкого качества, но быстрый (например, сеть автоматических метеостанций). Оказывается, есть способ скомбинировать эти источники, получив достаточно много достаточно хороших битов: нужно применить экстрактор . Это детерминированная функция, которой можно «скормить» небольшое количество почти идеальных случайных битов и очень много битов среднего качества, и получить большое число очень хороших случайных битов. В зависимости от того, как измеряется и чему равняется качество и количество битов на входе и выходе, определяется качество самого экстрактора. Вклад Вигдерсона состоит в разработке нескольких конструкций эффективных экстракторов. Наиболее известный инструмент — зигзаг-произведение, введенное в совместной работе с Салилом Вадханом и уже упомянутым Омером Рейнгольдом и нашедшее применение также в построении других объектов, например, экспандеров . Это графы, которые одновременно достаточно разрежены и хорошо связаны. Они используются в самых разных областях, но в том числе позволяют сократить количество случайных битов, которые использует вероятностный алгоритм. Экспандеры также известны как графы-расширители, а за другие их явные конструкции была вручена премия Абеля 2020 года . Итак, использование экстрактора позволяет достичь того же результата вычислений с использованием случайных битов худшего качества, а использование экспандера — с использованием меньшего количества случайных битов. А можно ли и вовсе избавиться от их использования и полностью дерандомизировать вероятностный алгоритм? Под дерандомизацией понимается преобразование вероятностного алгоритма в детерминированный, но имеющий нечто общее с исходным. Именно дерандомизацией был в конечном счете получен AKS-алгоритм проверки простоты. Алгоритм Рейнгольда побега из лабиринта Минотавра также получен из случайного блуждания при помощи экспандеров. Может быть, есть и универсальная процедура? С другой стороны, почему же она пока не открыта? Весьма удивительный ответ на этот вопрос дается в серии работ, из которых особенно выделяются статья Вигдерсона с Ноамом Нисаном «Трудность против случайности» («Hardness vs. Randomness») и две статьи Вигдерсона с Расселлом Импальяццо о дерандомизации при различных предположениях. В работе с Нисаном строится специальная конструкция генератора псевдослучайных чисел на основе произвольной «трудновычислимой» функции. Если эта функция по-настоящему трудновычислима, то генератор настолько хорош, что позволяет заменить вероятностную работу на ограниченный перебор. В работах с Импальяццо уточняется, при каких предположениях нужная трудновычислимая функция найдется. В первой из них она строится в предположении, что некоторые задачи из NP требуют обязательно либо экспоненциального перебора, либо экспоненциального предвычисления. (Технически это предвычисление определяется как микросхема, заранее изготовленная для задачи известного размера. Если этой микросхеме подать на вход условие задачи, она должна отдать на выходе правильный ответ.) Такое предположение (экспоненциальная гипотеза) сильнее, чем просто P≠NP, но более эффективных алгоритмов, чем экспоненциальные, для ряда NP-задач нет. Во второй статье с Импальяццо используется предположение без всяких микросхем и предвычислений. Условие заключается в том, что сила вероятностных алгоритмов хоть немного ограничена: BPP≠EXP, то есть хоть какая-то задача, решаемая детерминированно за экспоненциальное время, не может быть решена за полиномиальное время вероятностно. Удивительно, но пока что никто не умеет доказывать, что это верно. Заключение же теоремы слабее, чем в варианте с микросхемами: для любой задачи, решаемой вероятностно, есть достаточно быстрый (но не полиномиальный, а только субэкспоненциальный) детерминированный алгоритм, который решает эту задачу верно, но не всегда, а лишь для подавляющего большинства входов. Таким образом, на вопрос о силе рандомизированных алгоритмов можно ответить так. Если P=NP, то они ничего не дают (об этом было известно еще с начала 1980-х). Если NP «сильно больше» P, то они тоже ничего не дают. И только в промежутке между этими гипотезами вероятностные вычисления могут быть сильнее детерминированных. Все еще P≠NP Тут мы возвращаемся к центральной проблеме теоретической информатики и в некотором смысле всей математики — проблеме равенства P и NP. Почему большинство исследователей верят, что они не равны, но при этом не могут этого доказать? На первый вопрос ответов много, но одним из самых убедительных доводов является существование NP-полных задач (к ним относятся, например, судоку на поле N 2 x N 2 , «Морской бой» и «Сапер» — хотя насчет правильной формализации последнего все еще идут дискусии ). NP-полные задачи — «самые сложные»: к ним можно свести любую задачу из NP, так что если какая-то из них решается эффективно, то P=NP. Сводимость можно понимать как переформулировку одной задачи в терминах другой. Например, существование решения можно записать на формальном языке как математическую теорему, так что задача о доказуемости теорем будет NP-полной. Удивительно, что NP-полных задач очень много. Более того, подавляющее большинство задач из NP либо являются NP-полными, либо эффективно решаются непереборным алгоритмом (и потому лежат в P). Лишь для совсем небольшого числа задач вопрос классификации открыт, и со временем их число уменьшается (как с проверкой простоты). Полиномиальные алгоритмы могут быть весьма нетривиальными, как и доказательства NP-полноты. Тем не менее, нигде эти два множества не соприкасаются. Наблюдается эффект «невидимого забора»: ни один из методов, используемых для полиномиального решения, не работает для NP-полных задач, и ни один из инструментов доказательства NP-полноты не подходит для задач из P. При этом если бы P совпадало с NP, то полиномиальные и NP-полные задачи тоже были бы одним и тем же множеством! И что бы тогда означала та структура, которую мы наблюдаем? Однако несмотря на огромные усилия и даже объявленную премию в миллион долларов , никто не смог доказать, что P≠NP. За полвека исследований оказалось, что целые группы методов доказательства принципиально не могут сработать. Говорят о так называемых «барьерах» к доказательству. Первый из них — барьер релятивизации — был открыт еще в 1970-х. Можно помыслить компьютеры, подключенные к «черному ящику» — устройству, которое мгновенно решает заложенную в него задачу. Такие черные ящики называют «оракулами», и они способны значительно ускорить вычисления. При этом они могут ускорить и собственно вычисления, и проверку корректности решений, так что и класс P, и класс NP могут расшириться. Так вот, есть оракул, при котором P=NP, и есть оракул, при котором P≠NP. Это значит, что доказательство любого из этих фактов должно ломаться при вычислениях с оракулами, что исключает различные рассуждения, использующие диагональный метод. Но в 1980-х годах стали появляться комбинаторные рассуждения, которые преодолевали этот барьер. Появился такой план: попробовать доказать, что все задачи из P лежат в каком-то комбинаторно простом множестве, в котором не лежит какая-то задача из NP. Такого рода рассуждения стали называть естественными доказательствами. Однако этот план потерпел крах: оказывается, если существуют односторонние функции, то естественные доказательства не приведут к неравенству P и NP. Метафорически рассуждение можно изложить так: если P≠NP, то искать доказательства теорем сложно — но тогда сложно искать и доказательство того, что P≠NP. Затем, в 1990-х годах, появилось несколько замечательных теорем, доказанных при помощи алгебраических рассуждений о многочленах над конечными полями. Это, прежде всего, теорема IP=PSPACE и PCP-теорема. Они преодолевали оба известных барьера, и возникла надежда, что они пригодятся и для решения проблемы равенства P и NP. Однако Вигдерсон в соавторстве со Скоттом Ааронсоном воздвиг третий барьер, названный барьером алгебризации. Это аналог барьера релятивизации, но для оракулов специального вида — алгебраических. Таким образом, и алгебраические техники тоже были отброшены. Сейчас известны рассуждения, преодолевающие все три барьера, но как их приложить к проблеме P и NP, пока никто не знает. Мы упомянули лишь о некоторых темах, входящих в область научных интересов Вигдерсона. Конкретно они в той или иной степени связаны с определением границ того, что в принципе можно вычислить: сведение класса NP-задач к P, односторонние функции, доказательства с нулевым разглашением, генерация случайных битов, дерандомизация. Они не выстраиваются в прямую линию, но идут, скорее, по окружности. Помимо этого, Вигдерсон занимается сложностью доказательств, теорией распределенных вычислений, сложностью логических схем, алгоритмами дискретной оптимизации, теоретическими основами искусственного интеллекта и другими вопросами. Какой бы темой он ни занимался, в его работах сочетаются концептуальная глубина и красивейшая математика. Недавно он выпустил книгу «Mathematics and computation» , в которой описал личный взгляд на теорию сложности вычислений и использование в ней математических конструкций. Эта книга прекрасно подойдет для читателей, в некоторой степени уже знакомых с математикой и желающих получить общее представление о теоретической информатике. Даниил Мусатов