Чем известен лауреат Абелевской премии 2021 года

N+1Наука

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

Чем известен лауреат Абелевской премии 2021 года

Даниил Мусатов

17 марта Норвежская академия наук объявила лауреатов Абелевской премии 2021 года: ими стали Ласло Ловас и Ави Вигдерсон — за «фундаментальный вклад в теорию компьютерных наук и дискретную математику и ведущую роль в их формировании как центральных областей современной математики». По просьбе N + 1 о работах одного из лауреатов, Ави Вигдерсона, рассказывает Даниил Мусатов, доцент кафедры дискретной математики Физтех-школы прикладной математики и информатики МФТИ.

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

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

Ави Вигдерсон. Ednawig / wikimedia commons / CC BY-SA 4.0

P=NP?

Проблема равенства P и NP была поставлена ровно полвека назад, в 1971 году, независимо в работах американо-канадского математика Стивена Кука и советского математика Леонида Левина (позднее он также эмигрировал в США из-за политического преследования в СССР). Если говорить кратко, то проблема заключается в оценке алгоритмической сложности переборных задач.

Разберемся сначала, о каких задачах идет речь и что такое алгоритмическая сложность. Задачи здесь изучаются массовые, то есть содержащие бесконечное число различных формулировок: решить уравнение (x2 + 20x + 21 = 0) — это конкретная задача, а решить уравнение (x2 + px + q = 0) для всех p и q — массовая. Кроме того, мы ограничимся дискретными задачами с бинарным ответом. Дискретность означает, что условие записывается конечным числом битов — например, p и q должны быть целыми. Бинарность ответа означает, что ответ будет «да» или «нет»: нужно не найти решение, а указать, есть ли оно.

Нас будут интересовать алгоритмические решения, то есть компьютерные программы, которые принимают на вход условие задачи, и, проработав некоторое время, возвращают правильный ответ. Сложность задачи определяется временем работы алгоритма. Поскольку разных условий бесконечно много, смотрят не на конкретные числа, а на порядок роста времени решения в зависимости от размера задачи (в битах). Говорят, что алгоритм полиномиален, если время его работы растет как многочлен, то есть с задачами размера n алгоритм работает не дольше, чем cnd для некоторых констант c и d. На практике редко используют алгоритмы со степенью многочлена больше 3, но в теории полиномиальность считается синонимом вычислительной эффективности. Это может показаться странным: если время растет как n20, то работа с задачей из 10 битов потребует мощнейшего суперкомпьютера, а если время растёт как n100, то вычисления будут принципиально нереализуемы в силу физических причин. Почему же мы считаем такие алгоритмы эффективными? Во-первых, любая конкретная граница была бы произвольной и зависела бы от особенностей компьютерной архитектуры. Во-вторых, как правило, если какой-то полиномиальный алгоритм для решения задачи мы нашли, то дальше его можно улучшать, чтобы сделать реализуемым на практике.

Класс P как раз объединяет все задачи, для которых найдется хоть какой-то полиномиальный алгоритм.

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

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

В каждом примере возникает задача о наличии подходящей записи: есть ли решение у головоломки, реализуемы ли требования к расписанию, доказуема ли теорема и так далее. (В случае с теоремой важно, чтобы доказательство было полиномиальной длины). Подобные задачи и образуют класс NP. Их можно придумать огромное количество, и для решения каждой из них возникает переборный алгоритм: рассмотрим все допустимые записи и про каждую из них проверим, является ли она подходящей. В процессе такого перебора либо нужное решение найдется, либо станет ясно, что его не существует. Однако такой перебор будет слишком долгим — экспоненциальным, — и начиная с некоторого размера задачи компьютер с ним никогда не справится — ни существующий, ни любой мыслимый. Вопрос заключается в следующем: есть ли универсальный способ сократить такой огромный перебор до полиномиального, то есть включено ли NP в P?

Для некоторых задач сократить перебор можно: например, третий пример из списка выше соответствует известнейшей задаче о проверке числа на простоту (точнее, тут проверка обратная: есть ли у числа делитель, то есть является ли число составным). В 2002 году индийские математики Маниндра Агравал, Нирадж Каял и Нитин Саксена опубликовали алгоритм (ставший известным под названием AKS по первым буквам фамилий авторов), проверяющий простоту за полиномиальное время, и показали, что в этой задаче большой перебор не нужен. Тут стоит отметить, что многочлен измеряется не от самого числа, а от количества знаков в его десятичной записи, то есть от его логарифма.

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

Возможность криптографии

С другой стороны, P≠NP — необходимое требование для работы почти любых криптографических протоколов. Большинство из них можно взломать, перебрав возможные ключи или пароли, а их надежность строится на том, что такой перебор неосуществим, а более эффективных способов взлома нет. Если же P=NP, то такие способы есть и, вполне возможно, они осуществимы и на практике. Поэтому такое открытие поставило бы под угрозу все современное мироустройство, что обыграно в фильме Travelling Salesman.

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

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

P=BPP?

Авторизуйтесь, чтобы продолжить чтение. Это быстро и бесплатно.

Регистрируясь, я принимаю условия использования

Рекомендуемые статьи

3 ключа к скрытым ресурсам тела, сознания и души 3 ключа к скрытым ресурсам тела, сознания и души

Как добраться до внутреннего источника энергии

Psychologies
Правило трех вопросов. Эта проверенная в Гарварде техника поможет понравиться собеседнику Правило трех вопросов. Эта проверенная в Гарварде техника поможет понравиться собеседнику

Уточняющие вопросы сделает вас более привлекательным собеседником

Inc.
Похожи на кукол! Малиновская, Волкова и еще 9 звезд очень пожалевшие о пластике Похожи на кукол! Малиновская, Волкова и еще 9 звезд очень пожалевшие о пластике

В погоне за идеальным лицом они слишком увлеклись бьюти-тюнингом

Cosmopolitan
Только не три! Как исправить неудачное окрашивание бровей Только не три! Как исправить неудачное окрашивание бровей

Как скорректировать цвет бровей в домашних условиях?

Cosmopolitan
Как выглядят Моника Беллуччи, Джулия Робертс, Сигурни Уивер и другие звезды 90-х Как выглядят Моника Беллуччи, Джулия Робертс, Сигурни Уивер и другие звезды 90-х

Как выглядели в молодости популярные актрисы 90-х

Cosmopolitan
Почему в США был запрещен нарезанный хлеб? Почему в США был запрещен нарезанный хлеб?

История о том, как пальцы американских домохозяек оказались в опасности

Maxim
Эксперимент Muon g-2 увидел отклонения от Стандартной модели в измерениях магнитного момента мюона Эксперимент Muon g-2 увидел отклонения от Стандартной модели в измерениях магнитного момента мюона

Эксперимент Muon g-2 в Фермилаб представил первые результаты

N+1
Каким получился «Чернобыль» Данилы Козловского Каким получился «Чернобыль» Данилы Козловского

Почему «Чернобыль» Данилы Козловского не спорит с сериалом HBO, а дополняет его

РБК
Марки и овощной салат. Приглашение к обсуждению Марки и овощной салат. Приглашение к обсуждению

Современным детям часто кажется, что родители совсем о них не думают

СНОБ
Жить и есть в удовольствие! Жить и есть в удовольствие!

Как стать энергичнее и научиться правильному питанию без диет

Домашний Очаг
Петр I: коллекционер, исследователь, художник Петр I: коллекционер, исследователь, художник

Где Петр I обучался искусству графики и как отправился в Европу инкогнито?

Культура.РФ
Инфаркт, отит, усталость: что будет со здоровьем, если не ходить к зубному Инфаркт, отит, усталость: что будет со здоровьем, если не ходить к зубному

Несовершенная гигиена и невнимание к состоянию зубов грозят не только кариесом

Cosmopolitan
Как избавиться от запаха перегара: советы, которые тебе обязательно пригодятся Как избавиться от запаха перегара: советы, которые тебе обязательно пригодятся

Мифы о том, как избавиться от перегара, и реально работающие средства

Playboy
Победа киностудий: как «Оскар-2021» развенчал мифы о борьбе Голливуда и стримингов Победа киностудий: как «Оскар-2021» развенчал мифы о борьбе Голливуда и стримингов

Влияние стриминговых платформ на Голливуд и результаты премии — очередной миф

Forbes
Новый ISUZU D-Max и его железные аргументы Новый ISUZU D-Max и его железные аргументы

Новый ISUZU D-Max – новое поколение пикапов

4x4 Club
Уже не девочки: всё о личной жизни юных героинь из популярных сериалов нулевых Уже не девочки: всё о личной жизни юных героинь из популярных сериалов нулевых

Эти девочки прославились своими ролями в нулевые. А как они поживают сегодня?

Cosmopolitan
«Бедность наследуется»: правда ли это? «Бедность наследуется»: правда ли это?

Обречены ли вы на наследственную бедность и можно ли сломать этот сценарий?

Psychologies
Юпитер использовали как детектор темной материи Юпитер использовали как детектор темной материи

Физики изучили излучение Юпитера в поисках следов аннигиляции темной материи

N+1
Инструкция для отечественной торговли: есть ли кодекс профессиональной этики у современного искусства Инструкция для отечественной торговли: есть ли кодекс профессиональной этики у современного искусства

Зачем российскому рынку современного искусства профессиональная этика?

Forbes
«Я плакал в 10 раз больше, чем за всю свою жизнь. Мачизм как-то поубавился»: Олег Тиньков рассказал о борьбе с лейкемией «Я плакал в 10 раз больше, чем за всю свою жизнь. Мачизм как-то поубавился»: Олег Тиньков рассказал о борьбе с лейкемией

Олег Тиньков — как едва не отказался от лечения, и о планах развивать донорство

Esquire
Венчурный инвестор подсел на наркотики, азартные игры и женщин. Сможет ли он исцелиться и заслужить прощение? Венчурный инвестор подсел на наркотики, азартные игры и женщин. Сможет ли он исцелиться и заслужить прощение?

Подробный бизнес-план буйного кутежа

Inc.
«Колония — это не страшно»: Михаил Ефремов впервые рассказал о жизни за решеткой «Колония — это не страшно»: Михаил Ефремов впервые рассказал о жизни за решеткой

Михаил Ефремов рассказал о своей жизни в местах лишения свободы

Cosmopolitan
Остаться без дела: что делать менеджеру, если к нему пришли силовики Остаться без дела: что делать менеджеру, если к нему пришли силовики

Как вести себя при общении с представителями правоохранительных структур

Forbes
Ученые создали микрокапсулы-«пельмени» для адресной доставки лекарств Ученые создали микрокапсулы-«пельмени» для адресной доставки лекарств

Микрокапсулы могут доставлять препараты прямо к пораженным областям организма

Популярная механика
Нейробиологи впервые предотвратили трансформацию прионов в патогенную форму Нейробиологи впервые предотвратили трансформацию прионов в патогенную форму

Описаны переходные конформации патологического процесса превращения прионов

N+1
Манёвры на границе Манёвры на границе

Ограничения позволяют ребёнку расти свободным и самодостаточным

Здоровье
Аудиторы: Корпорация МСП неэффективна, стратегии не было и нет — зато средние зарплаты 600 тыс. рублей Аудиторы: Корпорация МСП неэффективна, стратегии не было и нет — зато средние зарплаты 600 тыс. рублей

Корпорация МСП незначительно повлияла на прогресс малого бизнеса в России

Inc.
Святая, которой отрезали совсем не волосы: кто был прототипом Рапунцель Святая, которой отрезали совсем не волосы: кто был прототипом Рапунцель

Жизнь девушки, ставшей прототипом Рапунцель, была страшнее, чем в сказках

Cosmopolitan
Правила жизни Владимира Ленина Правила жизни Владимира Ленина

Владимир Ленин: политика есть концентрированное выражение экономики

Esquire
Вечная память дресс-коду. Что такое «деловой гардероб» в 2021 году Вечная память дресс-коду. Что такое «деловой гардероб» в 2021 году

Как понимание дресс-кода трансформировалось на протяжении 50 лет

СНОБ
Открыть в приложении