Удаленное доказательство

Из семи Задач тысячелетия до сих пор решена только одна — гипотеза Пуанкаре, доказательство которой сформулировал Григорий Перельман. В начале сентября появились сообщения, что американский математик Мартин Доуд (Martin Dowd) справился с еще одной задачей из списка, сумев доказать неравенство классов P и NP. Но через пару недель математик удалил статью с доказательством. Мы попросили рассказать Владимира Потапова из Института математики имени Соболева СО РАН, что с доказательством Доуда было не так, и почему неравенство P и NP так важно.

Проблема, которую принято кратко записывать формулой «P ≠ NP?», пожалуй, вторая по числу опубликованных неверных решений после Великой теоремы Ферма и первая из до сих пор нерешенных. Почему эта проблема привлекает внимание множества математиков и даже совсем не математиков? Что означает ее решение для математики и для человечества?

Что такое «сложно»?

Начнем издалека — с понятия сложности. Точнее не сложности вообще, а более конкретно: вычислительной сложности задачи.

Перемножить в уме два целых числа обычно сложнее, чем их сложить, а возвести число в степень себя (x^x), как правило, вообще невозможно без вычислительной техники.

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

Можно полагать, что входными данными алгоритма является двоичное (или десятичное, это неважно) число, состоящее из n цифр. Число операций A(n), которые выполняет алгоритм для получения ответа, тоже зависит от n.

Например, в случае алгоритма сложения на вход подаются двоичные представления двух чисел, длина которых не превосходит n. Ясно, что их сумму можно получить за линейное относительно n число операций над битами (в случае десятичной записи — операций над десятичными цифрами). Более точное определение числа операций зависит от конкретного множества используемых элементарных операций и для нас сейчас неважно. Мы будем сортировать задачи по сложности — скорости роста функции A(n) — весьма грубо: линейный (в зависимости от n) рост сложности, полиномиальный рост и рост быстрее полиномиального.

На самом деле, поскольку у нас всего 2ⁿ различных наборов входных данных, мы можем заранее выписать все возможные 2ⁿ ответов, и алгоритм будет просто перебирать ответы, чтобы найти правильный. Тогда нам понадобится не более C(n)·2ⁿ операций, где C(n) — сложность проверки правильности ответа.

Решить или проверить?

В математике (и в жизни!) часто встречаются задачи, когда найти правильный ответ нелегко, а вот проверить правильность предъявленного ответа гораздо проще. Задачи, для которых сложность проверки ответа C(n) растет не более чем полиномиально, как раз и составляют класс NP. А те задачи, для которых сложность нахождения ответа A(n) растет полиномиально, составляют класс P.

Конечно, класс P содержится в классе NP — для проверки правильности ответа мы можем просто решить задачу. В знаменитой проблеме, которую мы сейчас обсуждаем, нужно выяснить, верно ли обратное: если решение задачи можно вычислительно просто проверить, то можно ли ее вычислительно просто решить?

С точки зрения здравого смысла это сомнительно. Например, рассмотрим задачу о нахождении гамильтонова цикла в графе. Пусть задан граф на n вершинах, то есть некоторый набор вершин (точек), в котором некоторые пары вершин соединены ребрами (отрезками), а некоторые нет. Нужно выяснить, найдется ли такой циклический путь по ребрам графа, который по разу проходит через все вершины (гамильтонов цикл). Ясно, что объем перебора всевозможных путей в графе быстро растет с ростом числа вершин и ребер.

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

Имеется и приближенный к реальности вариант этой задачи, известный как задача коммивояжера. Рассмотрим список городов, между которыми имеется авиасообщение и известны цены билетов. Можно ли посетить все города, затратив на перелеты не более M рублей?

Эти два примера относятся к задачам распознавания, поскольку требуют ответа в форме «да» или «нет». Известно, что при исследовании проблемы «P ≠ NP?» можно ограничиться только задачами распознавания. Отметим, что задачи распознавания тесно связаны с оптимизационными задачами.

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

Проблема «P ≠ NP?» и сам класс NP стали широко известны после результата, полученного в 1971 году Стивеном Куком, который доказал, что на самом деле все задачи из класса NP по существу сводятся к решению одной — самой сложной.

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

В англоязычной литературе теорему Кука чаще называют «теоремой Кука–Левина», по имени примерно в то же время доказавшего аналогичную теорему, тогда еще молодого советского математика Леонида Левина. Кандидатская диссертация Леонида Левина была провалена в 1971 году на заседании диссертационного совета в новосибирском Академгородке. Мы не будем здесь обсуждать, что послужило причиной такого результата голосования: качество оформления диссертации, попытка остановить научную карьеру сильного конкурента или, как сказано в Википедии, «неопределенность политического облика» соискателя.

Вскоре после публикации Кука, Ричард Карп предложил список из 21 NP-полной задачи. С тех пор математики серьезно разработали технику доказательства NP-полноты конкретной задачи и нашли ещё множество таких вычислительных задач. Нередко новые NP-полные задачи возникают путем введения дополнительных ограничений в условия NP-полной задачи, так, чтобы получившаяся подзадача сохраняла свойство NP-полноты. Теперь проблему определения NP-полноты задачи стало возможным ставить как массовую вычислительную задачу.

В 2020 году молодой российский математик Дмитрий Жук доказал известную гипотезу про то, что для некоторого класса ограничений само выяснение вопроса о том, приводят ли новые ограничения к полиномиальной разрешимости или сохраняют NP-полноту задачи, является полиномиально разрешимым. Его статья вызвала огромный интерес специалистов во всем мире, и Дмитрий Жук получил приглашение выступить на Международном конгрессе математиков, который в следующем году будет проходить в Санкт-Петербурге.

Многие задачи класса NP, подобно задаче коммивояжера, являются задачами оптимизации. Хорошие алгоритмы для их решения позволяют экономить ресурсы, время и деньги даже в тех случаях, когда удается найти только близкое к оптимальному решение или решение при наличии каких-то ограничений на параметры. Так что от доказательства равенства P = NP путем предъявления полиномиального решения NP-полной задачи можно ожидать большую экономическую пользу.

Односторонние функции

Как ни странно, доказательство неравенства P ≠ NP тоже востребовано на практике.

Для корректной работы многих современных криптографических протоколов нужны так называемые односторонние функции. Это такие функции f, для которых вычисление значения функции f(x) на любом аргументе x — простая операция, а вычисление прообраза x по значению функции f(x) — сложная.

Для построения криптосистемы нужно иметь одностороннюю функцию «с лазейкой». Лазейка — это такой секретный ключ y(f), с помощью которого прообраз x можно получить из f(x) за разумное время.

Рассмотрим, например, как работает процедура электронной идентификации. Вам нужно подтверждение от клиента, владеющего ключом y(f). Для этого вам не нужен секретный ключ y(f), достаточно только знания функции f. Вы произвольно выбираете x и посылаете клиенту f(x), если он в ответ посылает x, то у него есть ключ, а значит он действительно тот самый клиент.

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

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

Бреет ли брадобрей себя?

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

Проиллюстрируем диагональную конструкцию на примере придуманного Георгом Кантором доказательства несчетности множества вещественных чисел. Будем рассуждать от противного. Предположим, мы можем дать каждому вещественному числу из интервала (0,1) некоторый уникальный номер (натуральное число). Как известно, вещественное число представляется в виде десятичной дроби X = 0,x₁x₂... Можно считать, что десятичная дробь бесконечная, поскольку конечную десятичную дробь можно продолжить нулями. У i-го вещественного числа Z на i-ой позиции после запятой стоит какая-то цифра. Обозначим её через z_i. Рассмотрим число Y, в десятичной записи которого на i-ой позиции находится цифра z_i + 1 или цифра 0, когда z_i = 9. Число Y не может совпадать ни с каким занумерованным числом Z, поскольку различается с числом под номером i в i-ой позиции. Так мы получили противоречие с существованием нумерации всех вещественных чисел из интервала (0,1).

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

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

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

Григорий Перельман выкладывал свои знаменитые препринты на сайте arXiv.org, Мартин Доуд выложил статью на researchgate.net. Как ни огорчительно для «самодеятельных» авторов, репутация автора в математике весьма важна. Нет, не потому, что математики особенно склонны к чинопочитанию. Дело в другом. Чтобы специалист начал серьезно разбирать сложный математический текст, он должен верить (хотя бы не исключать), что в нем содержится заявленное доказательство.

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

Трудно сказать, была ли таким образом указана ли фатальная ошибка в аргументации Доуда или это только некоторый существенный пробел в доказательстве, но автор уже удалил свою статью с личной страницы в researchgate.net. Ошибки в доказательствах (не говоря уже о существенных пробелах в рассуждениях) случаются у всех, даже у великих. Кто их не делал — тот, вероятно, ничего сложного никогда и не пытался доказать.