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

3.4. Почему эти подходы не решили проблему P vs NP

Итак, мы рассмотрели три великих попытки вернуть субъекта в математику. Брауэр сказал: математика — это деятельность ума, а не склад платонических объектов. Марков сказал: математика — это деятельность алгоритма, а не созерцание истин. Мартин-Лёф сказал: доказательство — это программа, и если программа не компилируется, то у вас нет доказательства. Казалось бы, после таких заявлений проблема P vs NP должна была рассыпаться сама собой, как карточный домик под порывом ветра.

Не рассыпалась. Почему?

Каждый из трёх подходов совершил один и тот же подвиг: он вернул в математику различие между «построено» и «угадано». И каждый из трёх подходов совершил одну и ту же ошибку: он не различил «построено быстро» и «построено медленно». А проблема P vs NP — это именно о скорости.

Брауэр великолепно расправился с неконструктивными доказательствами существования. Он сказал: предъявите объект. Предъявите метод. Не можете — вы не математик, вы метафизик. Но он ничего не сказал о том, сколько времени должно занимать это предъявление. Интуиционистское доказательство существования может быть экспоненциально сложным — и с точки зрения Брауэра это нормально. Главное, что оно конструктивно. Главное, что объект строится, а не угадывается. А то, что строительство займёт время жизни Вселенной, — это уже не математический вопрос, а инженерный [87].

Марков пошёл дальше: он формализовал конструктивность через понятие алгоритма. Алгоритм либо есть, либо нет. Если есть — объект существует. Если нет — извините. Но Марков, как и Брауэр, не различал быстрые и медленные алгоритмы. Алгоритм полного перебора, работающий экспоненциальное время, — это с точки зрения конструктивной математики Маркова полноценный алгоритм. Он строит объект. Он доказывает существование. То, что его выполнение требует астрономического числа шагов, никого не волнует. Конструктивная математика гарантирует существование построения, но не гарантирует, что это построение можно дождаться [76].

Мартин-Лёф встроил конструктивность в синтаксис. В его теории типов нельзя доказать существование, не предъявив программу. Но — опять то же самое — теория типов ничего не говорит о сложности этой программы. Вы можете написать программу, которая перебирает все возможные сертификаты, пока не найдёт подходящий. Тип у такой программы будет правильный. Компилятор пропустит. Теорема доказана. А то, что программа работает экспоненциально долго, — это проблема hardware, а не mathematics [86].

Три великих революции. Три героических попытки. И один и тот же дефект: слепота к ресурсу. Слепота ко времени. Слепота к тому, что построение построению рознь, и что построение за экспоненциальное время — это практически та же фикция, что и платоническое существование, только растянутая во времени настолько, что никто не доживёт до её завершения.

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

В платоническом мире времени нет. Объекты не возникают и не исчезают. Они просто есть — всегда были и всегда будут. В таком мире вопрос «сколько времени займёт построение?» бессмыслен — потому что само понятие «займёт время» предполагает процесс, а процесс предполагает время, а время предполагает субъекта, который ждёт [88].

Математика, изгнавшая субъекта, изгнала и время. У неё нет часов. У неё есть только логическая выводимость: из A следует B, и не важно, сколько шагов вывода потребовалось. Теорема, доказанная за миллион страниц, и теорема, доказанная за три строчки, равноправны. Алгоритм, работающий экспоненциальное время, и алгоритм, работающий линейное время, — оба алгоритмы, и оба «существуют» в платоническом смысле.

Проблема P vs NP — это бунт времени против вечности. Это крик реальности о том, что ресурсы конечны. Это напоминание о том, что математика делается живыми людьми, у которых есть дедлайны, гранты и продолжительность жизни. И ответить на этот крик бессубъектная математика не может — потому что в её языке нет слова «успеть» [89].

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

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

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

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

Три великих альтернативных подхода не решили проблему P vs NP, потому что они решали другую проблему. Они решали проблему конструктивности — и решили её блестяще. Но проблема P vs NP — это не проблема конструктивности. Это проблема эффективной конструктивности. Это проблема ресурса. Это проблема времени.

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

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

3.5. Необходимость более глубокого основания: субъект и осознание

Мы перебрали всех героев. Брауэр хотел вернуть в математику ум, но не объяснил, что это такое. Марков хотел заменить ум алгоритмом, но не заметил, что алгоритмы бывают экспоненциальными и, следовательно, бесполезными. Мартин-Лёф построил математику, в которой доказательство компилируется, но компилятору всё равно, займёт ли выполнение программы секунду или тепловую смерть Вселенной.

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

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

Здесь мы подходим к центральному пункту, который отделяет гуманитарный метод от всех предыдущих попыток. Марков и Мартин-Лёф заменили субъекта алгоритмом. Это был колоссальный прогресс по сравнению с платонизмом, где субъекта не было вообще. Но это была замена одного неживого на другое.

Алгоритм — это не субъект. Алгоритм не устаёт. Алгоритм не хочет кушать. Алгоритму не нужно домой, к семье. Алгоритм может работать экспоненциальное время и не жаловаться. Алгоритму всё равно, закончится ли вычисление через секунду или через миллиард лет. У алгоритма нет желаний. У алгоритма нет потребностей. У алгоритма нет осознания.

Субъект — это не просто исполнитель инструкций. Субъект — это тот, кто ставит цель. Тот, кто хочет результата. Тот, кто ограничен во времени и в ресурсах. Тот, кто страдает, когда метод не находится. Тот, кто радуется, когда осознаёт, что он сделал.

Именно поэтому никакая формальная система, сколь угодно конструктивная, не может решить проблему P vs NP сама по себе. Потому что проблема P vs NP — это не проблема формальной системы. Это проблема субъекта. Это субъект спрашивает: «Могу ли я найти решение за разумное время?» Это субъект различает «быстро» и «медленно» — не потому, что у него есть формальное определение полиномиальности, а потому, что у него есть жизнь, которая конечна [91].

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

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

И именно это знание и есть критерий, отделяющий P от NP. P-задача — это задача, для которой метод может быть осознан. NP-задача — это ситуация, для которой метод не осознаётся, сколько ни бейся, потому что его там нет — есть только перебор или чудо.

Три богатыря пытались построить математику без чудес. Это была благородная цель. Но они не заметили, что чудеса можно маскировать под алгоритмы — достаточно сделать алгоритм экспоненциальным. И только осознание, только понимание «что я сделал» позволяет отличить настоящий метод от экспоненциальной имитации. Потому что метод можно осознать и передать другому. А экспоненциальный перебор нельзя осознать — можно только смириться с ним, как с неизбежным злом.

На этом мы заканчиваем историческую часть. Мы видели, как математика изгнала субъекта — и ослепла. Мы видели, как герои-одиночки пытались вернуть субъекта — и не смогли, потому что им не хватило понятия осознания. Теперь наша задача — построить альтернативу, которая не повторит их ошибок.

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

И здесь же, на самом пороге следующей части, введём важное терминологическое уточнение, которое избавит нас от двусмысленности. До сих пор мы, следуя традиции, говорили «NP-задача». Это было вынужденное подчинение чужому языку. Начиная с этого момента, мы будем называть вещи своими именами.

То, что в классической теории сложности именуется «NP-задачей», с точки зрения гуманитарного метода задачей не является. Задача — это то, у чего есть метод. То, что можно решить, осознавая свои действия шаг за шагом. То, что превращает желание в потребность через предъявление однозначного способа действия.

NP-сущность не такова. У неё нет метода. Есть предмет — свойства, которым должно удовлетворять решение. Есть возможность проверить, удовлетворяет ли предъявленный объект этим свойствам. Но метода построения нет. Он заменён либо перебором, либо угадыванием, либо чудом.

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

Разница между «задачей» и «ситуацией» — это и есть разница между P и NP. Задача имеет метод. Ситуация — нет. Задача решается. Ситуация разрешается — или не разрешается — сама. Задача превращает субъекта в мастера. Ситуация превращает субъекта в игрока.

Так что договоримся: P-задачи и NP-ситуации. Это не игра в слова. Это возвращение слову «задача» его первоначального смысла — того, который математика утратила вместе с субъектом. Задача — это когда ты знаешь, что делать. А когда не знаешь — это ситуация. И первое, чему учит гуманитарный метод, — это честно признаваться себе, в чём ты находишься: в задаче или в ситуации.

Теперь — к делу. К изложению самого метода.