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

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

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

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

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

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

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

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

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

Ирония судьбы: Аристотель, который подарил логике инструмент родо-видовых определений, прекрасно понимал его ограниченность. Для него определение через род и вид было лишь одним из способов познания — подходящим для классификации уже известного, но не для открытия нового. Рядом с этим методом у него существовал другой — учение о четырёх причинах, включая действующую причину (то, что производит изменение) и целевую причину (то, ради чего изменение происходит) [50].

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

2.4. Аксиома выбора: легализация неконструктивного

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

Формулировка аксиомы выбора настолько проста, что неподготовленный человек даже не заподозрит подвоха. Звучит она так: «Для любого семейства непустых множеств существует функция, которая выбирает по одному элементу из каждого множества этого семейства» [51]. Функция выбора. Берёт из каждой коробки по конфетке. Что может быть естественнее?

Если у вас есть конечное число конечных коробок, то никакой аксиомы не нужно. Вы просто подходите к каждой, запускаете руку и берёте что-нибудь. Это конструктивный процесс: вы знаете, что делать, вы делаете это шаг за шагом, и в конце у вас в руках — ровно по одному предмету из каждой коробки.

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

И вот тут на сцену выходит аксиома выбора. Она говорит: не парьтесь. Функция выбора существует. Не надо её строить, не надо предъявлять, не надо объяснять, как она работает. Просто поверьте: она есть. Где-то там, в платоновском мире, где уже лежат все математические объекты, лежит и эта функция. И вы имеете полное право её использовать в доказательствах.

Парадокс Банаха-Тарского, или Во что превращается геометрия с аксиомой выбора

Лучшая иллюстрация того, куда заводит аксиома выбора, — это знаменитый парадокс Банаха-Тарского, доказанный в 1924 году [52]. С помощью аксиомы выбора Стефан Банах и Альфред Тарский доказали, что трёхмерный шар можно разрезать на конечное число кусков, а затем собрать из этих кусков два шара, каждый из которых идентичен исходному. Без пустот. Без растяжений. Без изменения плотности. Просто переложили куски — и из одного шара получилось два.

Это не фокус. Это строгая математическая теорема, доказанная в ZFC. Если вы принимаете аксиому выбора, вы обязаны принять и то, что удвоение объёма — это просто вопрос правильной перегруппировки.

Разумеется, куски, на которые разрезается шар, невообразимо сложны. Они не измеримы в смысле Лебега — у них нет объёма [53]. Их нельзя предъявить физически. Их нельзя даже вообразить в виде чего-то, что можно «разрезать ножом». Это чисто платонические объекты, которые «существуют» только потому, что так сказали.

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

Эрнст Цермело и спор, который всё расставил по местам

Аксиома выбора вошла в математику не через парадную дверь, а через чёрный ход — и с грандиозным скандалом. В 1904 году Эрнст Цермело, пытаясь доказать теорему о том, что любое множество может быть вполне упорядочено, сформулировал принцип, который позже стал известен как аксиома выбора [54].

Реакция была мгновенной и яростной. Эмиль Борель, Анри Лебег, Анри Пуанкаре и другие ведущие математики того времени обрушились на Цермело с критикой, которая сегодня читается как провидческая [45]. Их аргумент был прост: нельзя утверждать существование объекта, для которого не предъявлен метод построения. «Выбрать» элемент из множества — это не магическое заклинание. Это действие. А действие требует действующего.

Особенно язвителен был Борель. Он писал, что аксиома выбора — это не математика, а метафизика. Что рассуждать о бесконечном числе произвольных выборов — это всё равно что рассуждать о Боге, который совершает эти выборы за нас. Что математика не имеет права постулировать существование того, что не может быть построено [55].

Но Цермело победил. Не потому, что его аргументы были сильнее. А потому, что без аксиомы выбора рассыпалась значительная часть математического анализа и теории множеств. Математикам пришлось выбирать: либо отказаться от огромного корпуса уже доказанных теорем, либо принять аксиому выбора вместе со всеми её парадоксальными следствиями. Они выбрали второе — и сделали вид, что это был свободный и осознанный выбор, а не капитуляция перед удобством [51].

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

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

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

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

А теперь — самое главное. Если вы приняли аксиому выбора, если вы согласились с тем, что «существует» не обязательно означает «можно построить», то вы потеряли право удивляться тому, что P, возможно, не равно NP.

P vs NP — это вопрос о том, можно ли быстро построить то, что можно быстро проверить. Это вопрос о том, эквивалентны ли конструктивное и неконструктивное существование — в мире полиномиального времени. Но математика в целом уже ответила на аналогичный вопрос — эквивалентны ли конструктивное и неконструктивное существование в принципе. И ответила: нет. Аксиома выбора — это и есть свидетельство о неэквивалентности. Мы постулируем существование объектов, которые не можем построить.

Так почему же математики удивляются, что в мире эффективных вычислений ситуация может оказаться такой же? Что разрыв между «проверить» и «найти» может быть фундаментальным, а не временным техническим затруднением?

Они не должны удивляться. Они сами создали прецедент. Они сами сказали: да, бывает так, что объект существует, но мы не знаем, как его получить. Аксиома выбора — это их собственная декларация о том, что P ≠ NP в общем случае. Осталось только осознать это применительно к миру полиномиальных вычислений.

2.5. Следствие: математика не различает «построено» и «угадано»

Итог прост, как приговор: современная математика принципиально не различает «построено» и «угадано».

Давайте проведём мысленный эксперимент. Представьте, что вы — математик, и вы доказываете теорему существования. Вы говорите: «Существует объект X, обладающий свойством P». Что именно вы утверждаете? Что вы можете предъявить X? Что вы знаете, как его построить? Что у вас есть метод, алгоритм, рецепт, инструкция? Вовсе нет. Вы утверждаете только одно: предположение о том, что такого объекта нет, приводит к противоречию. И всё.

Это классическое доказательство от противного. Вы не строили X. Вы не знаете, как он выглядит. Вы не можете его предъявить. Вы просто показали, что его несуществование логически несовместимо с вашими аксиомами. И математическое сообщество довольно кивает: доказательство существования состоялось [57].

Но теперь представьте, что вы — не математик, а инженер. Вам нужно построить мост. Вы приходите к начальнику и говорите: «Доказано, что мост существует». Начальник спрашивает: «Где чертежи?» Вы отвечаете: «Чертежей нет. Но предположение об отсутствии моста противоречит законам физики, следовательно, мост где-то есть». Долго ли вы проработаете на этой должности?

Математика, в отличие от инженерии, не требует предъявления объекта. Она удовлетворяется доказательством его существования. И до тех пор, пока математика остаётся игрой в символы на бумаге, это работает. Но как только математика пытается ответить на вопросы о реальном мире — о вычислениях, об алгоритмах, о том, что можно сделать за разумное время, — этот трюк перестаёт работать. Потому что в мире вычислений «существует» без «вот как это построить» — это пустой звук [58].

Философы давно заметили, что слово «есть» в математике употребляется в двух радикально разных смыслах. Первый смысл — конструктивный: «Я построил это, и вот оно». Второй смысл — платонический: «В мире идей это имеется, можете не сомневаться» [59].

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

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

Именно эта неразличимость и породила трагикомическую ситуацию с проблемой P vs NP. Вспомним формальные определения.

Класс P — это класс задач, для которых существует детерминированная машина Тьюринга, решающая задачу за полиномиальное время [17]. Класс NP — это класс задач, для которых существует недетерминированная машина Тьюринга, принимающая язык за полиномиальное время, или, что эквивалентно, существует полиномиальный верификатор [18]. В обоих случаях ключевое слово — «существует». Тот самый слепой, неразличающий квантор ∃.

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

Но формально, на языке ZFC, эти два «существует» выглядят одинаково. Оба утверждают существование некоторого конечного объекта (машины или сертификата). И математика, вооружённая только своим родо-видовым языком и своим неразличающим квантором, не может увидеть разницу между ними [60].

Хуже того: эта слепота институционализирована. Она встроена в саму ткань математического образования и математической практики. Студентов учат, что доказательство существования — это полноценный результат. Что конструктивное и неконструктивное доказательства равноценны. Что предъявить объект и доказать, что он не может не существовать, — это одно и то же.

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

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

2.6. Почему математика стала «слепой» к генезису

Мы проследили всю историю болезни. Платон подсадил математику на мир идей. Аристотель пытался предупредить. Кантор сделал актуальную бесконечность респектабельной. Аксиоматический метод превратил доказательство в игру в символы. Родо-видовые определения запретили говорить о процессе. Аксиома выбора узаконила существование без построения.

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

Ответов несколько, и ни один не делает математикам чести.

Причина первая: эстетическая трусость

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

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

За эту любовь к прекрасному они заплатили зрением. Статуя совершенна, но она не движется. Платонический объект безупречен, но у него нет истории. А генезис — это и есть история. Это рассказ о том, как нечто возникло. И математика, отказавшаяся от рассказа в пользу вечности, перестала понимать, откуда что берётся.

Причина вторая: удобство доказательств

Неконструктивное доказательство почти всегда короче конструктивного. Доказать, что объект существует, не предъявляя его, — это как выиграть спор, не приводя аргументов: достаточно поймать оппонента на противоречии самому себе. Быстро, дёшево, эффектно.

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

Математики, как и все люди, предпочитают лёгкие пути. Когда выяснилось, что неконструктивные доказательства позволяют публиковать больше статей, получать больше грантов и быстрее продвигаться по карьерной лестнице, выбор был сделан. Математический мейнстрим перешёл на неконструктивную логику не потому, что она «истиннее», а потому, что она «практичнее» [62].

Аристократический платонизм, презирающий суету построения, обернулся банальным карьеризмом. Чтобы публиковаться, не нужно ничего строить. Достаточно доказать, что существует. А на вопрос «почему?» всегда можно ответить: «Это следует из аксиомы выбора». И никто не спросит с вас чертежи.

Причина третья: страх перед субъектом

Но есть и более глубокая, почти психоаналитическая причина. Генезис — это всегда генезис для кого-то. Процесс построения требует строителя. Алгоритм требует исполнителя. Доказательство как действие требует того, кто доказывает.

Вернуть генезис в математику — значит вернуть субъекта. А субъект — это страшно. Субъект ошибается. Субъект сомневается. Субъект привносит в чистую науку что-то человеческое, слишком человеческое: интуицию, предпочтения, эмоции. Математика, мечтавшая стать абсолютно объективной, не могла допустить такого соседства [44].

Поэтому она избавилась от субъекта, как от ненужного свидетеля. Вместе с субъектом она избавилась и от генезиса — потому что одно без другого не существует. Не может быть процесса без того, кто его осуществляет. Не может быть построения без строителя. Не может быть алгоритма без исполнителя.

Математика предпочла мир, в котором никто ничего не делает. Объекты просто есть. Истины просто открываются. Доказательства просто существуют — как цепочки символов, которые никто не должен читать и понимать. Это мир без времени, без действия, без ответственности. Это мир, в котором математику не за что отвечать — потому что он ничего не создал, а только «открыл» то, что было всегда [63].

Причина четвёртая: успех ценой забвения

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

Математики рассудили просто: если метод даёт результаты, зачем задавать вопросы о его основаниях? Зачем копаться в философии, если можно просто публиковать статьи и получать признание? Прагматизм победил рефлексию [64].

Но у каждого успеха есть цена. Ценой этого успеха стала неспособность ответить на вопрос о P vs NP. Потому что этот вопрос — не о следствиях из аксиом. Он о том, как работает сама математика. Он требует от математики посмотреть на себя со стороны — а это именно то, чему математика сопротивлялась столетиями.

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

Результат этого выбора — перед нами. Неразрешимости. Парадоксы. Проблема P vs NP, которая не поддаётся никаким формальным методам, потому что она сформулирована в языке, который утратил способность различать построенное и угаданное.

Хватит ли у математики смелости признать, что она сама создала эту проблему и сама же должна её решить — вернув в себя то, что изгнала?

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

Именно это и предлагает гуманитарный метод, к изложению которого мы перейдем в следующей части. Но прежде чем строить новое, мы должны посмотреть, кто уже пытался это сделать до нас — и почему у них не получилось.

Глава 3. Попытки вернуть конструктивность (исторический обзор)

3.1. Интуиционизм Брауэра

Брауэр начал с простого, почти наивного вопроса: что такое математика? И дал ответ, от которого формалистов передёргивало: математика — это не набор теорем о платонических объектах. Математика — это деятельность человеческого ума. Она происходит в сознании математика, а не где-то там, в мире идей. Она строится, а не открывается [65].

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

Из этого следовал убийственный вывод, которого математическое сообщество не могло простить Брауэру: доказательство существования без предъявления объекта — это не доказательство. Если вы говорите «существует число с таким-то свойством», но не можете его предъявить или хотя бы указать метод его нахождения, — вы не математик. Вы болтун. Вы не построили число, вы просто произнесли заклинание [66].

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

Чтобы реализовать свою программу, Брауэр пошёл на шаг, который математики восприняли как акт интеллектуального терроризма. Он отказался от закона исключённого третьего.

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

Брауэр сказал: этот закон работает для конечных множеств, где можно перебрать все варианты. Но для бесконечных множеств он не работает — потому что вы не можете перебрать бесконечность и проверить, что искомый объект нигде не прячется [67]. Доказать, что объекта нет, не значит построить объект. Это значит лишь, что ваша система аксиом не противоречит его существованию. А это разные вещи.