Почему P-NP проблема такая сложная
(научно-непопулярный пост)
"Решения" P-NP проблемы публикуют в основном фрики. Дело не в том, что эти сотни попыток оказываются неудачными, а в том, что они еще и обнаруживают невежество их авторов, какие-то причудливые представления о математике и её методах, безумное самомнение и пр. Раньше то же самое творилось с великой теоремой Ферма. Этим грешат как "положительные" решения (предположительно полиномиальные алгоритмы), так и "отрицательные".
С алгоритмами вообще беда. По идее, если уж человек верит в то, что сейчас перевернет всю computer science, всю криптографию и значительную часть machine learning, то хорошо бы ему все-таки написать тестовую реализацию, и проверить её на каких-нибудь примерах (о сомнениях, которые высказывал, в частности, avva, насчет потенциальной экзотической сложности вроде О(n10100) я помню, но к этим экземплярам они не относятся). Пусть написанная программа, например, отвечает на вопросы, может ли заданное двадцатизначное число быть представлено в виде произведения двух меньших, одно из которых начинается с заданных цифр (достаточно очевидно, как такой вопрос записать в форме инстанса SAT-задачи с небольшим, в общем-то, количеством переменных). Если ей это удастся (но ей этого не удастся), то после этого будет уже неважно, насколько хорошо автор умеет писать статьи, насколько чисто он доказал, что его алгоритм работает, и т.п. Само существование подобной программы уже будет феерической победой: из нее очевидным образом делается быстрая факторизация.
С доказательствами беда немного другая: если они вообще осмысленные (а не состоят из шизофазии), то читатель, как правило, в какой-то момент встречает утверждение "любой алгоритм решения должен быть построен по такой-то схеме, и сейчас мы поймем, почему эта схема не может работать на задачах такого-то класса". Нет, не должен.
Вот сейчас я попробую описать разновидность алгоритмов решения канонической NP-полной задачи, а именно k-SAT. Алгоритмы эти довольно неожиданного типа, содержат красивый трюк, и мне нравится думать, что я изобрел их первым (хотя наверняка я ошибаюсь, и Валиант сделал это раньше). Разумеется, они "не работают": среди них, кажется, нет такого, который работал бы за полиномиальное время (хотя, вообще-то, я не могу этого доказать). Однако они интересны тем, что если сузить на них предполагаемое P!=NP, из этого немедленно следуют довольно неочевидные вещи из области, хм, как бы назвать эту часть математики? Из области матанализа, видимо, пусть это и "школьное" название. Итак.
Давайте выберем для иллюстрации, и чтобы привыкнуть к обозначениям, какую-нибудь k-SAT формулу. Например, такую:
(a|!b|!c)(a|!b|c)(!a|!b|!c)(!a|!b|c)(a|b|c)(!a|b)
В ней 3 переменных и 6 клашей. Спойлер: она выполнима, выполняющая подстановка a=0, b=0, c=1.
Общая идея алгоритмов предлагаемого класса состоит в сопоставлении каждой SAT-формуле многочлена следующим образом. Для формулы, состоящей из n переменных и m клашей, мы строим многочлен с m переменными, представляющий собой произведение n сомножителей вида "моном + моном". Каждая переменная многочлена соответствует клашу исходной, а каждый сомножитель соответствует некоторой переменной; в каком-то смысле это она же, вывернутая наизнанку (я бы употребил слово "двойственный", но это не совсем корректно, т.к. сопоставление не взаимно однозначно). Сомножитель, соответствующий переменной х, строится следующим образом: перемножаем переменные, соответствующие тем клашам, в которые он входит "утвердительно" (это первый моном), и переменные, соответствующие клашам, в которые входит отрицание этой переменной (это второй моном), и складываем их. Например, из формулы выше мы получим следующий многочлен:
(ABE+CDF)(EF+ABCD)(BDE+AC)
Здесь первая скобка соответствует переменной а, вторая - b, третья - с. Новые переменные A, B, C, D, E, F соответствуют клашам с первого по шестой.
Что случится, если раскрыть скобки в получившемся многочлене? Сделать это эффективно (то есть так, чтобы результатом можно было воспользоваться в полиномиальном алгоритме) невозможно, поскольку в итоге получится 2n мономов. Тем не менее, давайте посмотрим на результат такой операции. Каждому возможному набору значений переменных k-SAT формулы соответствует ровно один моном. Удовлетворяющим подстановкам соответствуют мономы, содержащие все переменные многочлена (некоторые, возможно, не в первой степени).
Теперь мы можем сформулировать интересное свойство такого многочлена: исходная формула имеет удовлетворяющую подстановку тогда и только тогда, когда m-тая смешанная производная этого многочлена (по всем переменным) отлична от нуля.
Тут уже становится интересно. Понятно, как оценить её, вычислив значения многочлена в 2m точках. Нельзя ли сделать это быстрее? Мотивирующий пример: m-тую производную по одной и той же переменной можно оценить, вычислив его значения всего в m+1 точке.
Я умею доказывать, что не существует линейной комбинации из менее, чем 2m значений функции в фиксированных точках, которая точно вычисляла бы значение m-той смешанной производной произвольного многочлена от m переменных. Даже это - нетривиальный факт, его доказательство примерно устанавливает предел сложности рассуждений, которые я могу провести в уме в метро, я придумал его не сразу, и оно кажется мне красивым (поскольку опирается на свойства редко встречающейся и несколько абсурдной операции покомпонентного умножения векторов в линейном пространстве). Как можно обосновать невозможность не просто её вычислить (не обязательно в вещественных или комплексных числах - в любом поле, а то и в более общей структуре какой-нибудь), но хотя бы отличить нули от целых не-нулей? Моей математической подготовки для этого уже не хватает.
Мало того. Используя теорему Валианта-Вазирани, мы выясняем, что достаточно отличать нулевую производную от единственного другого её значения, игнорируя все остальные случаи. Мало того, мы ведь не о какой-то "функции вообще", данной нам в виде черного ящика. У нас тут многочлен со специальной структурой. Рассматривая (тоже NP-полную) задачу под названием read-thrice k-SAT (разновидность k-SAT, в которой каждая переменная содержится не более чем в трех clashes), мы можем потребовать, чтобы в каждом его сомножителе участвовало не больше трех переменных; это дает нам целые подпространства значений размерности (m-1), заполненные тождественными нулями, то есть можно считать, что значения во всех этих точках за нас уже "вычислены". И это еще не все трюки, которые можно придумать.
----
Я это рассказываю в ЖЖ, почти в пустоту, просто чтобы не пропадало. Вдруг кому пригодится. Я знаю, что серьезные журналы давно не принимают статей с доказательствами NP-полноты очередных задач, потому что штамповать такие статьи слишком просто. Тем не менее, мне кажется, что у Estimating high order mixed derivatives is NP-hard шансы были бы, именно потому, что это не штамповка вида "соберем из прутиков модель пружинок, из которых в [2] уже была собрана модель шестеренок, к которым в [1] сведена задача о палочках, сведение 3-SAT к которой содержится в классической работе [3]". Если кто-то решит в рассуждениях выше навести строгость, и такую статью оформить, ну мало ли, конецгодаплангорит, то имейте в виду, что я совершенно не против. Я не учони, мне неважно. Разве что напишите мне об этом, чтобы я был в курсе.
"Решения" P-NP проблемы публикуют в основном фрики. Дело не в том, что эти сотни попыток оказываются неудачными, а в том, что они еще и обнаруживают невежество их авторов, какие-то причудливые представления о математике и её методах, безумное самомнение и пр. Раньше то же самое творилось с великой теоремой Ферма. Этим грешат как "положительные" решения (предположительно полиномиальные алгоритмы), так и "отрицательные".
С алгоритмами вообще беда. По идее, если уж человек верит в то, что сейчас перевернет всю computer science, всю криптографию и значительную часть machine learning, то хорошо бы ему все-таки написать тестовую реализацию, и проверить её на каких-нибудь примерах (о сомнениях, которые высказывал, в частности, avva, насчет потенциальной экзотической сложности вроде О(n10100) я помню, но к этим экземплярам они не относятся). Пусть написанная программа, например, отвечает на вопросы, может ли заданное двадцатизначное число быть представлено в виде произведения двух меньших, одно из которых начинается с заданных цифр (достаточно очевидно, как такой вопрос записать в форме инстанса SAT-задачи с небольшим, в общем-то, количеством переменных). Если ей это удастся (но ей этого не удастся), то после этого будет уже неважно, насколько хорошо автор умеет писать статьи, насколько чисто он доказал, что его алгоритм работает, и т.п. Само существование подобной программы уже будет феерической победой: из нее очевидным образом делается быстрая факторизация.
С доказательствами беда немного другая: если они вообще осмысленные (а не состоят из шизофазии), то читатель, как правило, в какой-то момент встречает утверждение "любой алгоритм решения должен быть построен по такой-то схеме, и сейчас мы поймем, почему эта схема не может работать на задачах такого-то класса". Нет, не должен.
Вот сейчас я попробую описать разновидность алгоритмов решения канонической NP-полной задачи, а именно k-SAT. Алгоритмы эти довольно неожиданного типа, содержат красивый трюк, и мне нравится думать, что я изобрел их первым (хотя наверняка я ошибаюсь, и Валиант сделал это раньше). Разумеется, они "не работают": среди них, кажется, нет такого, который работал бы за полиномиальное время (хотя, вообще-то, я не могу этого доказать). Однако они интересны тем, что если сузить на них предполагаемое P!=NP, из этого немедленно следуют довольно неочевидные вещи из области, хм, как бы назвать эту часть математики? Из области матанализа, видимо, пусть это и "школьное" название. Итак.
Давайте выберем для иллюстрации, и чтобы привыкнуть к обозначениям, какую-нибудь k-SAT формулу. Например, такую:
(a|!b|!c)(a|!b|c)(!a|!b|!c)(!a|!b|c)(a|b|c)(!a|b)
В ней 3 переменных и 6 клашей. Спойлер: она выполнима, выполняющая подстановка a=0, b=0, c=1.
Общая идея алгоритмов предлагаемого класса состоит в сопоставлении каждой SAT-формуле многочлена следующим образом. Для формулы, состоящей из n переменных и m клашей, мы строим многочлен с m переменными, представляющий собой произведение n сомножителей вида "моном + моном". Каждая переменная многочлена соответствует клашу исходной, а каждый сомножитель соответствует некоторой переменной; в каком-то смысле это она же, вывернутая наизнанку (я бы употребил слово "двойственный", но это не совсем корректно, т.к. сопоставление не взаимно однозначно). Сомножитель, соответствующий переменной х, строится следующим образом: перемножаем переменные, соответствующие тем клашам, в которые он входит "утвердительно" (это первый моном), и переменные, соответствующие клашам, в которые входит отрицание этой переменной (это второй моном), и складываем их. Например, из формулы выше мы получим следующий многочлен:
(ABE+CDF)(EF+ABCD)(BDE+AC)
Здесь первая скобка соответствует переменной а, вторая - b, третья - с. Новые переменные A, B, C, D, E, F соответствуют клашам с первого по шестой.
Что случится, если раскрыть скобки в получившемся многочлене? Сделать это эффективно (то есть так, чтобы результатом можно было воспользоваться в полиномиальном алгоритме) невозможно, поскольку в итоге получится 2n мономов. Тем не менее, давайте посмотрим на результат такой операции. Каждому возможному набору значений переменных k-SAT формулы соответствует ровно один моном. Удовлетворяющим подстановкам соответствуют мономы, содержащие все переменные многочлена (некоторые, возможно, не в первой степени).
Теперь мы можем сформулировать интересное свойство такого многочлена: исходная формула имеет удовлетворяющую подстановку тогда и только тогда, когда m-тая смешанная производная этого многочлена (по всем переменным) отлична от нуля.
Тут уже становится интересно. Понятно, как оценить её, вычислив значения многочлена в 2m точках. Нельзя ли сделать это быстрее? Мотивирующий пример: m-тую производную по одной и той же переменной можно оценить, вычислив его значения всего в m+1 точке.
Я умею доказывать, что не существует линейной комбинации из менее, чем 2m значений функции в фиксированных точках, которая точно вычисляла бы значение m-той смешанной производной произвольного многочлена от m переменных. Даже это - нетривиальный факт, его доказательство примерно устанавливает предел сложности рассуждений, которые я могу провести в уме в метро, я придумал его не сразу, и оно кажется мне красивым (поскольку опирается на свойства редко встречающейся и несколько абсурдной операции покомпонентного умножения векторов в линейном пространстве). Как можно обосновать невозможность не просто её вычислить (не обязательно в вещественных или комплексных числах - в любом поле, а то и в более общей структуре какой-нибудь), но хотя бы отличить нули от целых не-нулей? Моей математической подготовки для этого уже не хватает.
Мало того. Используя теорему Валианта-Вазирани, мы выясняем, что достаточно отличать нулевую производную от единственного другого её значения, игнорируя все остальные случаи. Мало того, мы ведь не о какой-то "функции вообще", данной нам в виде черного ящика. У нас тут многочлен со специальной структурой. Рассматривая (тоже NP-полную) задачу под названием read-thrice k-SAT (разновидность k-SAT, в которой каждая переменная содержится не более чем в трех clashes), мы можем потребовать, чтобы в каждом его сомножителе участвовало не больше трех переменных; это дает нам целые подпространства значений размерности (m-1), заполненные тождественными нулями, то есть можно считать, что значения во всех этих точках за нас уже "вычислены". И это еще не все трюки, которые можно придумать.
----
Я это рассказываю в ЖЖ, почти в пустоту, просто чтобы не пропадало. Вдруг кому пригодится. Я знаю, что серьезные журналы давно не принимают статей с доказательствами NP-полноты очередных задач, потому что штамповать такие статьи слишком просто. Тем не менее, мне кажется, что у Estimating high order mixed derivatives is NP-hard шансы были бы, именно потому, что это не штамповка вида "соберем из прутиков модель пружинок, из которых в [2] уже была собрана модель шестеренок, к которым в [1] сведена задача о палочках, сведение 3-SAT к которой содержится в классической работе [3]". Если кто-то решит в рассуждениях выше навести строгость, и такую статью оформить, ну мало ли, конецгодаплангорит, то имейте в виду, что я совершенно не против. Я не учони, мне неважно. Разве что напишите мне об этом, чтобы я был в курсе.