P не равно NP: Доказательство, которое математики не поймут

Сергей Дегтярев

P не равно NP: Доказательство, которое математики не поймут

Часть I. КРИЗИС БЕССУБЪЕКТНОЙ МАТЕМАТИКИ

Глава 1. Неразрешимость: симптом, а не болезнь

1.1. Проблемы Гильберта и программа формализации

В 1900 году на Международном конгрессе математиков в Париже Давид Гильберт, признанный король математического цеха, огласил список из 23 проблем, которые, по его мнению, должны были определить развитие математики на столетие вперед [1]. Это был не просто список задач, а дерзкая, почти высокомерная заявка: математика всемогуща, и скоро у нее будет ответ на любой вопрос. Девизом Гильберта, который позже высекут на его надгробии, было: «Мы должны знать — мы будем знать» [2]. Забавно, что это высекли как раз перед тем, как его программа с треском провалилась.

Самой амбициозной среди поставленных задач была, пожалуй, вторая — проблема непротиворечивости арифметики. Гильберт хотел доказать математическими же средствами, что в математике никогда не возникнет противоречий. Вы не можете доказать, что 2+2=5. Никогда. Это звучало здраво: если уж мы строим Храм Абсолютного Знания, хорошо бы убедиться, что фундамент не сделан из песка [3].

Из этой идеи выросла так называемая программа Гильберта — грандиозный план по полной формализации всей математики. Замысел был дьявольски изящен в своей наивности:

Формализовать: Переписать всю математику на мёртвом, но кристально чистом формальном языке, превратив доказательства в подобие шахматных ходов. Никакой психологии, никакой интуиции, никаких «мне кажется». Только символы и правила их перестановки [4].

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

Доказать непротиворечивость: С помощью финитных, «абсолютно надежных» методов, в которых никто не мог бы усомниться, доказать, что из аксиом системы невозможно вывести 0=1. То есть доказать безошибочность «машины истины» [1][3].

Решить проблему разрешения (Entscheidungsproblem): Найти универсальный, механически исполняемый метод, который для любого математического утверждения определял бы, истинно оно или ложно. Фактически, создать супер-алгоритм, делающий математиков не нужными [5].

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

Живой, сомневающийся, ошибающийся и осознающий субъект — сам Гильберт, его ученики, любой математик — из этой картины мира методично изгонялся. На его место водружался бездушный механический оракул. Ирония в том, что именно попытка построить этот математический рай без субъекта и породила тех демонов, которые мучают науку о вычислениях до сих пор. О том, как ангелы формализма получили по заслугам от Гёделя и Тьюринга, поговорим в следующей главе.

1.2. Теоремы Гёделя о неполноте: первый удар

Пока Гильберт и его школа наводили бюрократический порядок в математике, в Вене подрастал Курт Гёдель — человек, которому суждено было стать Иудой формалистской программы. В 1931 году он опубликовал работу, содержавшую две теоремы, которые не просто пробили брешь в борту корабля Гильберта, а, по сути, показали, что корабль был спущен на воду уже с пробоиной [6].

Первая теорема, или «Всегда найдется то, чего вы не докажете»

Первая теорема Гёделя о неполноте утверждает, что любая формальная система, достаточно мощная, чтобы выразить арифметику (то есть способная оперировать натуральными числами и сложением-умножением), обречена на неполноту [7]. Это не вопрос сложности системы; это её врожденный дефект.

Идея гениальна в своем коварстве. Гёдель показал, как на строгом языке арифметики можно построить утверждение, которое говорит о самом себе: «Это утверждение недоказуемо в данной системе» [8]. Представьте себе робота-судью, который выносит вердикт: «Данное предложение является ложью». Если робот признает его истинным, то он подтверждает собственную лживость. Если ложным — то он опровергает истину. Система, столкнувшись с таким «гёделевским предложением», впадает в ступор. Она не может ни доказать его, ни опровергнуть, не разрушив собственной логической состоятельности. Оно истинно (мы это видим извне системы), но недоказуемо внутри неё [9].

Это был удар под дых «программе Гильберта». Оказалось, что математическая истина — это не просто результат механического вывода из аксиом. Всегда остается «истина вне клетки», которую видит живой субъект, но не видит формальный автомат.

Вторая теорема, или «Дурак с идеальной картиной мира»

Если первая теорема была болезненной, то вторая стала унизительной. Гёдель доказал: ни одна такая система не может доказать собственную непротиворечивость [10].

Гильберт требовал от математиков предъявить финитное доказательство того, что их игра в символы никогда не приведет к 0=1 Гёдель ответил: внутри самой системы это сделать невозможно в принципе. Чтобы доказать непротиворечивость арифметики, вам понадобится более мощная система. А чтобы доказать непротиворечивость той — еще более мощная. И так до бесконечности. Математики, мечтавшие построить Храм Истины на незыблемом фундаменте, вдруг обнаружили, что этот фундамент висит в пустоте, а чертежи здания бесследно исчезли.

И здесь мы подходим к аналогии, которая объясняет это дилетанту лучше любых учебников. Представьте себе спор в социальных сетях. Ваш оппонент — человек с предельно простой, детской картиной мира, состоящей из трёх аксиом вроде «все политики воруют», «во всем виноваты рептилоиды», а его любимый интернет-портал всегда говорит правду.

С точки зрения формальной логики, его система одновременно и полна, и непротиворечива. У него есть простой ответ на любой вопрос — он не страдает от мук гёделевской неполноты, потому что его убогая аксиоматика недотягивает до мощности арифметики. И что самое главное, в рамках его системы, где любое неудобное вам доказательство объявляется «фейком», он совершенно прав, и его картина мира блестяще непротиворечива. Он, как и требовал Гильберт, доказал свою непротиворечивость своими собственными средствами — просто объявив все внешние аргументы несуществующими.

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

Так первый удар по программе изгнания субъекта был нанесен. Оказалось, что сложная система без познающего субъекта — слепа и не может обосновать даже собственную безвредность. А простая и самодостаточная — это и есть тот самый дурак, с которым бесполезно спорить. Программа Гильберта, таким образом, обещала нам либо паралич, либо идиотию.

1.3. Проблема остановки Тьюринга: алгоритмическая неразрешимость

Пока математический мир приходил в себя после гёделевской бомбардировки, за дело взялся Алан Тьюринг. В 1936 году он опубликовал работу, которая добила центральный пункт программы Гильберта — проблему разрешения, — но сделала это настолько элегантно, что математикам оставалось лишь молча страдать [11].

Тьюринг изобрел свою знаменитую машину — абстрактное вычислительное устройство с бесконечной лентой и конечным набором состояний, — пытаясь формализовать не что иное, как работу скучающего клерка. Машина могла читать символы, писать их, двигать ленту туда-сюда и переходить из состояния в состояние [12]. Вся современная компьютерная индустрия, все серверные фермы и смартфоны — это, по сути, потомки представления Тьюринга о том, как выглядит механическое мышление.

Ирония в том, что Тьюринг изобрел эту машину не чтобы создать компьютер, а чтобы доказать: есть вещи, которые она никогда не сможет вычислить [11].

Для решения Entscheidungsproblem — найти универсальный метод, определяющий истинность любого математического утверждения, — Тьюринг сначала показал, что это эквивалентно задаче о том, остановится ли когда-нибудь произвольная программа на произвольном входе [13]. Если бы существовал алгоритм, решающий проблему остановки, то был бы и алгоритм, решающий любую математическую проблему. Мечта Гильберта могла бы сбыться.

А затем Тьюринг продемонстрировал, почему эта мечта несбыточна в принципе. Его доказательство — это логическая ловушка, достойная дзенского коана [14].

Предположим, пишет Тьюринг, что такой волшебный алгоритм HALT(P, I) существует. Вы даете ему на вход программу P и данные I, а он выдает ответ: «остановится» или «не остановится». Раз он существует, мы можем его использовать как деталь для другой программы.

Теперь построим программу-паразита. Назовем ее BUSTER. Она принимает на вход другую программу Q и делает следующее:

Вызывает оракула HALT(Q, Q). То есть спрашивает: «Остановится ли программа Q, если скормить ей саму себя?»

Если оракул говорит «да, остановится», то назло ему уходит в бесконечный цикл.

Если оракул говорит «нет, не остановится», то BUSTER немедленно останавливается.

Программа BUSTER — это логический вандал. Она делает ровно противоположное тому, что предсказывает оракул.

Теперь подставим BUSTER саму в себя. Мы запускаем BUSTER(BUSTER). Спрашиваем оракула: «Остановится ли BUSTER(BUSTER)?»

Попытка первая. Оракул говорит: «Да, остановится». Тогда BUSTER, следуя своему коду, уходит в бесконечный цикл. Оракул ошибся. Попытка вторая. Оракул говорит: «Нет, не остановится». Тогда BUSTER немедленно останавливается. Оракул снова ошибся.

Оракул, предсказывающий поведение любой программы, не может существовать, потому что всегда можно построить программу, которая загонит его в противоречие [15]. Проблема остановки алгоритмически неразрешима. А с ней неразрешима и проблема разрешения Гильберта.

Самое убийственное в доказательстве Тьюринга — это роль наблюдателя. Мы, люди прекрасно видим, что оракул HALT обречен. Мы понимаем противоречие. Мы осознаем, почему BUSTER его взламывает. Но сам алгоритм HALT никогда не сможет этого понять. Он просто машина.

Формальная система, какой бы мощной она ни была, всегда может быть взломана конструкцией, которая использует её собственные правила против неё самой. И тот, кто видит этот взлом, — это не аксиома, не правило вывода, не автомат. Это субъект.

Тьюринг, в отличие от Гильберта, не пытался изгнать субъекта. Он поместил его в центр доказательства — как того, кто способен на рефлексию, на взгляд со стороны, на понимание предела формального [12]. Машина может вычислить что угодно, но она не может вычислить собственную остановку. А субъект — может.

Так второй удар по бессубъектной математике был нанесен. Оказалось, что не только истина (Гёдель), но и само понятие вычислимости (Тьюринг) ускользает от формальной системы, если в неё не включен тот, кто на эту систему смотрит.

1.4. Проблема P vs NP: эффективная неразрешимость

Если Гёдель и Тьюринг имели дело с абсолютными границами познания — можно ли вообще доказать или вычислить нечто, — то проблема P vs NP бьёт куда обиднее. Она не спрашивает, можно ли решить задачу в принципе. Ответ почти всегда «да»: обычный перебор вариантов рано или поздно сработает. Вопрос в том, можно ли решить задачу до того, как Солнце погаснет [16].

Формально проблема P vs NP была сформулирована в начале 1970-х годов, хотя её корни уходят глубже — в работы по математической логике и только зарождавшейся теории вычислений. Класс P (polynomial time) — это задачи, для которых существует алгоритм, работающий полиномиальное время. Удвоился размер входа — время выросло в разумное число раз. Это «хорошие», ручные задачи. Сортировка списка, поиск кратчайшего пути в графе, проверка числа на простоту — всё это P [17].

Класс NP (nondeterministic polynomial time) — это задачи, для которых проверить предъявленный ответ можно быстро, за полиномиальное время. А вот найти этот ответ — вопрос отдельный [18]. Задача коммивояжёра (найти кратчайший маршрут, проходящий через все города), разложение числа на множители, составление школьного расписания без конфликтов, упаковка чемодана — всё это NP [19].

Вопрос «P = NP?» звучит как невинная детская загадка: если решение можно быстро проверить на правильность, можно ли его так же быстро найти? Или быстрая проверка — это насмешка вселенной, которая показывает нам ответ, но отказывается объяснить, как к нему прийти?

Великое переселение народов: NP-полнота

В 1971 году Стивен Кук взорвал ситуацию, доказав теорему, которую математики до сих пор не могут ему простить [20]. Он показал, что задача о выполнимости булевых формул (SAT) является NP-полной. Это означало: если кто-то когда-нибудь найдет полиномиальный алгоритм для одной-единственной SAT, то автоматически все задачи из NP перейдут в P. Буквально. Лавина сойдёт.

За этим последовал каскад открытий. Ричард Карп в 1972 году опубликовал список из 21 классической задачи, доказав их NP-полноту через сведение к SAT [21]. Клика, гамильтонов цикл, задача коммивояжёра, рюкзак — все они оказались эквивалентны в своей вычислительной трудности. Открой метод для одной — и ты решил их все. Именно этот факт превратил проблему P vs NP из технического вопроса в одну из семи «Задач тысячелетия», за решение которой Математический институт Клэя в 2000 году назначил премию в миллион долларов [16].

Деньги лежат до сих пор.

Где здесь Бог? Оракулы и позор метода релятивизации

Самое унизительное в проблеме P vs NP — это не её нерешённость, они терпеливы и столетиями могут ждать решение проблем, а то, что математики не могут доказать даже возможность её решения имеющимися средствами.

В 1975 году Теодор Бейкер, Джон Гилл и Роберт Соловей опубликовали результат, который должен был бы заставить математиков усомниться в самих основаниях своего ремесла [22]. Они показали, что существуют воображаемые миры — так называемые «оракульные» модели вычислений, — в которых P = NP. И одновременно существуют другие, столь же логически непротиворечивые миры, в которых P ≠ NP.

О чём это говорит? О том, что стандартный метод доказательства в теории сложности — метод релятивизации, то есть рассуждение, которое не зависит от конкретных свойств модели, — принципиально бессилен ответить на вопрос P vs NP. Вы можете строить сколь угодно изощрённые конструкции, но если ваше доказательство «переживает» добавление произвольного оракула, оно не решит проблему. Вы просто докажете, что в мире A — да, а в мире B — нет [23].

Это был момент, когда математическое сообщество, ослеплённое верой во всемогущество формальных методов, получило пощёчину от самой логики. Машина формального вывода, которую они строили со времён Гильберта, сказала им: «Ребята, этим инструментом вы тут ничего не сделаете».

Ликбез для тех, кто ещё не бросил читать: что такое оракул и почему его добавление — это проверка на профпригодность

Чтобы понять масштаб катастрофы, устроенной Бейкером, Гиллом и Соловеем, нужно разобраться с терминологией. Математики обожают называть простые вещи сложными именами, чтобы никто не догадался, как всё на самом деле убого. «Оракул» — прекрасный тому пример.

Оракул в теории сложности — это воображаемая чёрная коробочка, которая мгновенно и бесплатно решает какую-то задачу [22]. Вы подсовываете ей вопрос, она — хоп! — и выдаёт ответ, не тратя ни единого вычислительного такта. Это как если бы ваша программа могла позвонить Богу и спросить: «Слушай, а этот конкретный гамильтонов цикл тут есть или как?» — и Бог бы ответил, не требуя за это процессорного времени.

Физически такой коробочки не существует. Но логически ничто не мешает нам её вообразить и рассуждать о классах сложности, которые получаются, если у машины Тьюринга есть доступ к такому чуду. Так появляются классы вроде P с оракулом для задачи A (обозначается P^A) — это задачи, которые можно решить за полиномиальное время, если у вас под столом живёт джинн, мгновенно решающий A [22].

А теперь — момент, ради которого всё это затевалось.

Доказательство «переживает» добавление произвольного оракула, если оно остаётся верным независимо от того, какой именно джинн сидит у вас под столом [23]. Если вы доказали, что P ≠ NP, и ваше доказательство «релятивизуется» (ещё одно словечко, означающее «работает с любым оракулом»), то оно должно работать и в мире, где оракул решает все возможные задачи за одну операцию, и в мире, где оракул бесполезнее калькулятора.

В чём подвох? А в том, что Бейкер, Гилл и Соловей предъявили два конкретных оракула. Для одного из них P = NP (то есть в этом мире быстрая проверка и быстрое нахождение ответа совпадают). Для другого — P ≠ NP (то есть быстрая проверка есть, а быстрого нахождения нет, идите перебирайте) [22].

Если бы существовало релятивизующееся доказательство того, что P = NP, оно бы доказывало это равенство и для того мира, где оно на самом деле неверно. И наоборот: релятивизующееся доказательство того, что P ≠ NP, сломало бы тот мир, где равенство есть. Противоречие.

Иными словами, любой стандартный метод доказательства, который не использует специфику отсутствия оракула в нашем реальном мире, обречён на провал [23]. А почти все методы, которыми математики умеют пользоваться — диагонализация, симуляция, комбинаторные построения — как раз таковы. Они слишком тупы, чтобы заметить разницу между реальностью и фантазией с оракулом.

Это как если бы следователь пытался доказать вину подозреваемого, используя метод, который одинаково хорошо доказывает вину и невиновного. Суд такое «доказательство» выбросит в мусорную корзину. Но математики, в своём высокомерном самолюбовании, десятилетиями пытались решить P vs NP именно такими методами — и только в 1975 году им ткнули носом в то, что их инструментарий непригоден.

Так что оракул — это не просто забавная абстракция. Это унизительный детектор профнепригодности для математического аппарата всей теории сложности. И аппарат этот проверку не прошёл.

Так в чём же проблема?

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

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

Проблема P vs NP, возможно, не решается так долго именно потому, что математики пытаются решить её в языке, который не различает «построено» и «угадано». Они ищут алгоритм там, где его не может быть по определению.

1.5. Общий корень: исключение субъекта из формальной системы

Итак, мы имеем три, казалось бы, разные катастрофы. Гёдель: в любой достаточно сильной системе есть истинные, но недоказуемые утверждения [7]. Тьюринг: нельзя алгоритмически определить, остановится ли произвольная программа [11]. Кук—Карп—Левин: скорее всего, быстрая проверка решения не гарантирует быстрого нахождения оного, и доказать это имеющимися средствами, похоже, невозможно [22].

Математики привыкли думать, что это три отдельные неприятности, как три разных болезни, поразившие организм их науки. Но что, если это не три болезни, а три симптома одной и той же? Что, если общий корень всех трёх катастроф — это методичное, педантичное, доведённое до абсурда исключение познающего субъекта из формальной системы? Акт коллективного самоубийства, растянутый на столетия.

Проследим маршрут этого интеллектуального харакири.

Шаг первый: Декарт. Он совершает гениальное открытие: «Я мыслю, следовательно, я существую». Субъект становится фундаментом достоверности. Казалось бы, вот оно, начало пути к зрелой науке, которая учитывает наблюдателя. Но нет. Математики прочитали Декарта и вынесли из него не важность субъекта, а важность метода. Субъект им понадобился лишь как трамплин, чтобы прыгнуть в объективное, а сам трамплин — за ненадобностью сжечь.

Шаг второй: Ньютон и Лейбниц. Они создают математический анализ — инструмент невероятной мощи. Но посмотрите, как они его строят. Они говорят о «бесконечно малых», о «стремлении к пределу», о «флюксиях». В этом языке ещё слышен шёпот субъекта: процесс, движение, стремление — это то, что происходит с кем-то, кто движется. Но математикам этот шёпот мешает. Им нужна тишина вечных, застывших истин.

Шаг третий: Коши и Вейерштрасс. Они совершают «очищение» анализа. Вон интуицию. Вон движение. Вон «стремление». Вместо живого процесса — мёртвая логика эпсилон-дельта. «Предел» перестаёт быть тем, к чему кто-то стремится, и становится набором символов, которыми жонглируют по формальным правилам [24]. Субъект, наблюдающий процесс, изгнан. Остался автомат для верификации утверждений.

Шаг четвёртый: Фреге, Рассел, Гильберт. Они решают, что анализа недостаточно. Нужно формализовать всё. Вообще всё. Чтобы от математика осталась только функция проверки доказательств, которую можно доверить машине. Математика должна стать игрой в символы по правилам, где смысл не нужен, а истина — это просто свойство синтаксической выводимости [3].

И вот он, результат. Грандиозный проект формализации завершён. В математике больше нет субъекта. И тут-то всё и начинает сыпаться.

Что общего между тремя нашими катастрофами? В каждой из них формальная система сталкивается с явлением, которое она не может «ухватить» именно потому, что исключила того, кто на неё смотрит.

Гёдель строит предложение «Я недоказуемо». Чтобы понять, что это предложение истинно, нужно выйти за пределы системы и посмотреть на неё со стороны [9]. Нужен субъект. Формальный автомат, который просто перекладывает символы по правилам, никогда не поймёт, что гёделевское предложение говорит о нём самом. Он его просто не увидит. Истина ускользает от автомата, но не от субъекта.

Тьюринг строит программу-паразита BUSTER, которая взламывает гипотетический алгоритм HALT. Чтобы построить BUSTER, нужно понять логику HALT и намеренно сделать наоборот. Нужен субъект, который видит систему извне и осознаёт её пределы [14]. Машина HALT не может осознать собственный предел. А Тьюринг — может.

P vs NP. Здесь та же история, но замаскированная под техническую проблему. NP-задача — это задача, в которой условие сформулировано для готового, актуально данного объекта («существует гамильтонов цикл»). P-задача — это задача, в которой условие определяет пошаговый метод построения («на каждом шаге выбирай непройденное ребро»). Первая формулировка не требует субъекта: объект просто есть или нет в платоновском мире. Вторая требует: метод — это то, что кто-то осуществляет во времени [25].

И вот математики, столетиями изгонявшие субъекта, внезапно спрашивают: «Можно ли всякий актуально данный объект превратить в потенциально построенный?» Не замечая, что сам вопрос возможен только для того, кто видит разницу между «дано» и «построено». Для автомата этой разницы нет. Для него оба класса выглядят как «существует сертификат». А раз они выглядят одинаково, то и доказать их различие автомат не может.

Исключение субъекта создало в математике гигантское слепое пятно. В этом пятне исчезло различие между:

— Актуальным и потенциальным (готовым объектом и процессом его построения);

— Родо-видовым определением и конструктивным определением («это есть то-то» против «сделай раз, сделай два»);

— Проверкой и поиском (верификацией сертификата и нахождением оного);

— Существованием и построением (платоническим «есть» и алгоритмическим «получится»).

Математика, построенная на теории множеств с аксиомой выбора, — это наука о том, что существует. Она принципиально не различает объекты, которые можно построить, и объекты, которые просто «есть» в силу аксиомы [26]. Но проблема P vs NP — это как раз вопрос о том, совпадают ли эти два класса: то, что можно быстро построить, и то, что можно быстро проверить.