P не равно NP: Доказательство, которое математики не поймут
- -
- 100%
- +
Спрашивать об этом математику, которая не различает «построено» и «существует», — всё равно что спрашивать слепого о цвете обоев. Он может дать ответ, но этот ответ не будет иметь отношения к тому, о чём вы спросили.
Именно поэтому Бейкер, Гилл и Соловей и обнаружили, что стандартные методы бессильны [22]. Стандартные методы — это методы математики, исключившей субъекта. Они не видят разницы между построением и существованием. А значит, они не могут доказать несовпадение того, что для них неразличимо.
Так три величайшие катастрофы математики XX века складываются в одну: исключение субъекта не усилило математику, а ослепило её. Оно породило парадоксы (Гёдель), неразрешимости (Тьюринг) и проблемы, которые невозможно решить имеющимися средствами (P vs NP). Храм Истины, построенный на изгнании того, кто познаёт, оказался храмом с заколоченными окнами. В нём всё верно, всё строго, всё формально — и ничего не видно.
1.6. Парадокс как симптом: система не видит собственных оснований
Итак, мы провели вскрытие. Перед нами труп формалистской мечты, и мы смотрим на него с патологоанатомическим интересом. Что же его убило? Гёдель, Тьюринг и проблема P vs NP — это не убийцы, как могло показаться. Это всего лишь симптомы. Болезнь, сожравшая организм математики изнутри, куда глубже.
Когда система кричит о помощи
Представьте себе человека, который приходит к врачу и жалуется на боль в груди. Врач-формалист диагностирует «проблему боли в груди» и выписывает обезболивающее. Через месяц пациент умирает от инфаркта. Врач записывает в отчёте: «Проблема решена: боль устранена, пациент жалоб не предъявляет».
Именно так математики XX века работали с собственными парадоксами. Они не спрашивали: «Почему система порождает эти противоречия?» Они спрашивали: «Как залатать дыру, чтобы продолжать делать вид, что всё в порядке?»
Бертран Рассел в 1901 году показал, что наивная теория множеств Кантора приводит к противоречию: множество всех множеств, не содержащих себя, одновременно и содержит себя, и не содержит [27]. Это был не мелкий баг — это был крах основания. Математики бросились латать: Рассел и Уайтхед написали трёхтомник «Principia Mathematica», где на доказательство того, что 1+1=2, ушла почти тысяча страниц [28]. Цермело и Френкель придумали аксиоматику ZFC, где множество всех множеств просто объявили вне закона, как будто достаточно таблички «Не влезай — убьёт», и проблема исчезнет [26].
Они устранили парадокс, но не спросили: а почему вообще возникла эта ситуация? Почему наивное, интуитивное, «человеческое» понятие множества привело к противоречию? Не потому ли, что формализация попыталась имитировать работу субъекта, который всегда знает границу между «думать о множестве» и «включать множество в само себя», — но имитировать без субъекта, на голых символах?
Эпименид-критянин говорит: «Все критяне лжецы». Это утверждение не может быть ни истинным, ни ложным, не породив противоречия [29]. Гёдель превратил этот древний парадокс в математический молот и разнёс им программу Гильберта [8]. Но что такое парадокс лжеца? Это утверждение, которое ссылается на само себя. Которое говорит: «Я ложно». Чтобы его оценить, нужен тот, кто стоит вне утверждения и смотрит на него. Нужен субъект.
Математики, исключившие субъекта, оказались беззащитны перед самореференцией. Формальная система не может осмыслить утверждение о самой себе — для этого ей нужен внешний наблюдатель. Но внешний наблюдатель и есть тот самый изгнанный субъект.
В 1922 году Туральф Сколем показал, что любая формальная теория множеств имеет счётную модель, даже если она утверждает существование несчётных множеств [30]. Говоря простым языком: говорят «есть несчётные множества», но на самом деле описывают их таким языком, что внутри этой теории вы никогда не сможете построить «настоящую» несчётность. Несчётность существует только для того, кто смотрит извне системы. Для самой системы её нет.
Это как если бы карта говорила: «На территории есть гора Эверест», а сама карта была бы размером с почтовую марку. Для того, кто смотрит на карту, Эверест реален. Для самой карты — это просто клякса краски определённой формы.
Парадокс — это не ошибка, это сигнал
Общий корень всех этих парадоксов — самореференция, помноженная на отсутствие субъекта. Формальная система, исключившая наблюдателя, не может помыслить собственные основания. Она не может провести границу между собой и миром, который описывает [31].
Парадокс — это крик системы о том, что она наткнулась на свой собственный предел. Это не баг, а фича. Это не ошибка в расчётах, а единственный доступный системе способ сообщить: «Я не знаю, где я заканчиваюсь и начинается реальность. Мне нужен тот, кто на меня смотрит».
Но математики, влюблённые в свою формальную девственность, проигнорировали этот крик. Они заклеили дыры аксиоматическими пластырями и продолжили делать вид, что всё в порядке.
Результат предсказуем. Система, которая не видит собственных оснований, обречена порождать неразрешимости. Она как робот, который пытается починить сам себя. Он может перебирать свои детали, оптимизировать алгоритмы, но он никогда не узнает, почему он был создан, какие аксиомы заложил в него программист-субъект, и что делать с командой, которая противоречит его базовой логике.
P vs NP как финальный диагноз
Теперь мы можем посмотреть на проблему P vs NP не как на техническую трудность, а как на симптом финальной стадии болезни. Это не просто вопрос о том, можно ли быстро решать задачи, ответы на которые быстро проверяются. Это вопрос о том, может ли формальная система осознать разницу между тем, что ей дано (актуальный объект), и тем, что она должна построить (потенциальный процесс).
Парадокс здесь глубже, чем кажется. Чтобы доказать, что P ≠ NP, математикам нужно показать, что существует класс задач, где быстрая проверка возможна, а быстрое решение — нет. Но чтобы это показать, им нужно различать «проверить» и «решить». А их основной инструментарий — формальные системы типа ZFC — принципиально не различает эти два модуса существования.
Это как если бы вам нужно было доказать, что кошки отличаются от собак, но у вас в распоряжении был бы только датчик, который и тех и других определяет как «животное». Технически он работает безупречно. Но вашу задачу он решить не может.
Математики потратили столетия, чтобы построить совершенную формальную систему. Они изгнали из неё всё человеческое: интуицию, движение, время, субъекта. Они хотели получить абсолютную истину, а получили абсолютную слепоту.
Их система идеально непротиворечива — но только до тех пор, пока не спрашивает о собственных основаниях. Их доказательства безупречны — но только до тех пор, пока не касаются различия между тем, что построено, и тем, что угадано. Их наука — вершина интеллектуального могущества, которая не может ответить на вопрос, почему она работает.
Парадокс, как мы выяснили, — это не ошибка. Это единственный честный голос в этом хоре самообмана. Это крик системы о том, что она умирает без того, кого изгнала.
Глава 2. Математика как наука без наблюдателя
2.1. От Платона до Кантора: торжество актуальной бесконечности
Прежде чем хоронить формалистскую программу, стоит понять, откуда вообще взялась эта странная идея — что математика может обойтись без субъекта. Корни этой идеи уходят так глубоко, что математики предпочитают о них не вспоминать: это портит им репутацию трезвомыслящих прагматиков.
Всё началось с Платона — человека, который был настолько недоволен окружающим миром, что изобрёл запасной. В его философии существует два мира: мир вещей, где всё течёт, портится и умирает, и мир идей, где всё совершенно, вечно и неизменно [32]. Математические объекты — числа, геометрические фигуры, отношения — обитают именно там, в мире идей. Они не создаются математиком. Они открываются, как уже существующие.
Это был гениальный пиар-ход. Объявив математические истины вечными и несотворёнными, Платон разом освободил математиков от необходимости объяснять, откуда берутся их объекты. Они не творят — они созерцают. Они не строят — они припоминают. Математик — это не инженер, а жрец, которому дозволено заглядывать в божественный чертёж [33].
Так в математику вошла идея актуальной бесконечности — бесконечности как завершённого, данного сразу и целиком объекта. Множество всех натуральных чисел не строится шаг за шагом. Оно просто есть — сразу, целиком, со всеми своими элементами. Вам не нужно считать до бесконечности, чтобы работать с бесконечностью. Она уже готова, упакована и ждёт вас на складе платоновского гипермаркета.
У Платона был ученик, который пытался предупредить человечество о грядущей катастрофе. Аристотель различал два вида бесконечности [34]. Потенциальная бесконечность — это процесс, который никогда не заканчивается: можно всегда добавить ещё единицу, можно всегда разделить отрезок пополам. Актуальная бесконечность — это бесконечность как готовая вещь: множество, которое бесконечно сейчас, в настоящем, как завершённый объект.
Аристотель настаивал: математика может пользоваться только потенциальной бесконечностью. Актуальная бесконечность — это философская фикция, источник парадоксов, за которую не стоит хвататься голыми руками [35].
Две тысячи лет математики ворчали, но в основном слушались. Они пользовались бесконечностями, но всегда оговаривались: «это просто способ выразиться», «мы имеем в виду, что процесс можно продолжать сколь угодно долго». Актуальная бесконечность оставалась табу.
Справедливости ради надо признать: попытки говорить о бесконечности конструктивно были. И самые блестящие умы античности демонстрировали, как это делается, не скатываясь в платонический гипноз. Евклид, доказывая бесконечность множества простых чисел, не говорит: «Представьте себе актуально бесконечное множество всех простых чисел». Он говорит: «Возьмите любое конечное множество простых, перемножьте их и прибавьте единицу — получите число, которое либо само простое, либо делится на простое, не входящее в ваше множество. Следовательно, никакое конечное множество не исчерпывает всех простых». Это чистое аристотелевское рассуждение в терминах потенциальной бесконечности: что бы вы ни построили, всегда можно построить ещё. Никакого «множества всех простых чисел» как готового объекта здесь не требуется [40].
Это принципиально иной тип мышления, чем канторовский. Евклид не нуждается в платоновском складе, где «уже лежат» все простые числа. Ему достаточно правила, которое позволяет по любому конечному списку построить следующее. Бесконечность здесь — не объект, а процесс.
Но именно этот тип мышления математики и выбросили на свалку, когда приняли теорию множеств как универсальный фундамент. Они предпочли склад — стройплощадке.
В конце XIX века Георг Кантор совершил то, что сейчас назвали бы стартап-пивотом: он превратил табу в товар [36].
Кантор создал теорию множеств — математику, которая работает с актуальной бесконечностью напрямую, без уверток и оговорок. Множество всех натуральных чисел — это объект, с которым можно обращаться как с готовым. Более того, Кантор показал, что бесконечностей много. Есть счётная бесконечность (натуральные числа), а есть несчётная (действительные числа). И это не просто фигура речи — это строгое математическое утверждение, доказанное диагональным методом [37].
Математическое сообщество взбесилось. Анри Пуанкаре, светило французской математики, называл теорию множеств «болезнью, от которой математика когда-нибудь излечится» [38]. Леопольд Кронекер, учитель Кантора, публично третировал его как «научного шарлатана» и «развратителя юношества» [39]. Борьба была настолько ожесточённой, что Кантор, человек с неустойчивой психикой, провёл последние годы жизни в клиниках для душевнобольных, переключаясь между математикой и богословием.
Но победил именно он, потому что его теория работала. Она давала результаты. Она позволяла доказывать теоремы, которые без неё были недоступны. А математики, при всех своих претензиях на чистоту, — люди практичные. Если инструмент работает, он будет использован, даже если его философские основания подозрительны.
Торжество канторовской теории множеств было полным и безоговорочным. К началу XX века математика перешла на язык множеств. Аксиоматика ZFC стала стандартом. Актуальная бесконечность из philosophia non grata превратилась в рабочую лошадку, на которой ездят, не задавая вопросов.
Но цена этого триумфа оказалась чудовищной — и мы её уже видели в первой главе.
Во-первых, актуальная бесконечность стёрла различие между «построено» и «существует». В платоновском мире все объекты уже есть. Математик их не создаёт — он их находит. А раз так, то нет нужды в методе построения. Достаточно доказательства существования. Аксиома выбора, одна из самых спорных аксиом ZFC, говорит: из любого семейства непустых множеств можно выбрать по элементу — и плевать, что никакого правила выбора не существует. Объекты выбраны, потому что они «есть» [26]. Это вершина бессубъектной математики: действие без действующего, выбор без выбирающего.
Во-вторых, смазалось различие между потенциальным и актуальным. Алгоритм — это потенциальная бесконечность: процесс, который разворачивается во времени. Сертификат — это актуальная бесконечность: готовый объект, предъявленный для проверки. Но для математики на ZFC и то и другое — просто множества. Разница между ними исчезает, как исчезает разница между снимком живого и движением мёртвого.
В-третьих, субъект был окончательно и бесповоротно вычеркнут из онтологии математики. В платоновском мире нет математика. Есть только объекты и отношения между ними. Тот, кто познаёт, стал лишним в науке о познании.
Математики заключили сделку с дьяволом актуальной бесконечности, и дьявол их, как водится, обманул. Он дал им невероятную мощь — возможность работать с бесконечностями как с готовыми объектами. А взамен отобрал зрение — способность видеть разницу между тем, что построено своими руками, и тем, что просто постулировано как существующее.
Именно эта слепота и породила все те парадоксы и неразрешимости, которые мы разбирали в первой главе. Гёдель, Тьюринг, проблема P vs NP — всё это не баги, а фичи мира, в котором актуальная бесконечность победила.
Ирония в том, что математики до сих пор не осознали, что их главная нерешённая проблема — P vs NP — это не технический вопрос. Это счёт, который выставила им реальность за столетия жизни в платонической грёзе. И счет этот, похоже, нечем оплатить — если не вернуть в математику того, кого из неё изгнали.
2.2. Аксиоматический метод: истина без субъекта
Если Платон создал мифологию, а Кантор — бизнес-модель, то аксиоматический метод стал логистической инфраструктурой бессубъектной математики. Это конвейер, по которому платоновские идеи доставляются из мира вечных сущностей в мир публикаций и грантовых заявок. И, как любой конвейер, он спроектирован так, чтобы ни один живой человек не мешал его работе.
От Евклида до Гильберта: как аксиомы перестали быть очевидными
Формально аксиоматический метод старше платонизма. Евклид, написавший свои «Начала» около 300 года до нашей эры, уже пользовался им вовсю: пять постулатов, из которых дедуктивно выводятся теоремы геометрии [41]. Но у Евклида аксиомы — это не произвольные соглашения. Это самоочевидные истины. «Через две точки проходит прямая» — кто же будет с этим спорить? Аксиома для грека — это то, что достойно принятия. Истина, которая видна любому, у кого есть глаза и разум.
Но шли века, и самоочевидность испарялась. Пятый постулат Евклида о параллельных прямых мучил математиков две тысячи лет: слишком сложный, слишком похожий на теорему, слишком… неочевидный. Когда Лобачевский и Бойяи в XIX веке построили геометрию, в которой пятый постулат не выполняется, а через точку проходит бесконечно много параллельных, это был шок [42]. Оказалось, что можно построить другую геометрию, столь же логичную, но с другими аксиомами… неочевидными.
Математики сделали из этого неверный вывод. Вместо того чтобы сказать: «О, так истина зависит от того, кто и как смотрит на мир», они сказали: «О, так истина вообще не зависит от того, кто смотрит. Аксиомы — это просто правила игры. Выбирайте любые, лишь бы они не противоречили друг другу» [43].
Аксиоматический метод в его современном виде — это конвейерная линия. У вас есть сырьё (аксиомы), у вас есть правила обработки (правила вывода), и у вас есть готовая продукция (теоремы). Субъект на этой линии — лишняя деталь, от которой желательно избавиться.
В идеале процесс доказательства должен быть настолько механическим, чтобы его могла выполнять машина Тьюринга — что, собственно, и требовалось по программе Гильберта [3]. Математик-человек — это всего лишь несовершенный прототип автомата для верификации. Он ошибается, устаёт, хочет кушать. Его нужно заменить. А пока не заменили — пусть сидит и проверяет, что цепочка символов, которую он вывел, соответствует формальным правилам.
В этой модели нет места ни интуиции, ни пониманию, ни озарению. Более того, эти человеческие качества объявляются подозрительными. Если вы «интуитивно чувствуете», что теорема верна, но не можете предъявить формальный вывод — вы не математик. Если вы «понимаете», почему утверждение должно быть истинным, но не можете записать это понимание в виде последовательности логических шагов — ваше понимание ничего не стоит [44].
Математика, построенная на аксиоматическом методе, — это математика, в которой эпистемология (учение о том, как мы познаём) полностью оторвана от онтологии (учения о том, что существует). Что существует — решают аксиомы. Как мы об этом узнаём — не важно. Субъект познания исчезает, остаётся только объект познания, подвешенный в логическом вакууме.
Но есть один вопрос, который аксиоматический метод принципиально не может решить, не выстрелив себе в ногу. Вопрос этот звучит так: кто выбирает аксиомы?
Аксиоматическая система — это машина. Она перемалывает аксиомы в теоремы. Но она не может выбрать себе аксиомы сама. Аксиомы должны быть заданы извне — субъектом.
Вот он, тот самый изгнанный субъект, который возвращается, как призрак отца Гамлета, в самый неподходящий момент. Вы выгнали его из процесса доказательства — он вернулся в процесс выбора оснований. Вы построили идеально объективную фабрику истины — но кто-то должен был выбрать, на каком сырье эта фабрика работает.
ZFC не упала с неба. Её выбрали люди — Цермело, Френкель, Сколем и другие — на основании своих интуитивных представлений о том, как должны вести себя множества [26]. Аксиома выбора была предметом ожесточённых споров десятилетиями. Её не «вывела» формальная система — её приняли субъекты на основании внематематических, философских аргументов [45].
То же самое с логикой. Классическая логика с законом исключённого третьего — это не божественное откровение. Это выбор, который сделали математики. Интуиционисты во главе с Брауэром предложили другую логику, без закона исключённого третьего, и построили на ней свою, конструктивную математику [46]. Это была полноценная, работающая альтернатива. Но математический мейнстрим выбрал классическую логику — потому что она удобнее, потому что она мощнее, потому что она позволяет доказывать больше теорем. Не потому что она «истиннее», а потому что она практичнее.
Иными словами, в самом сердце аксиоматического метода, замаскированное под объективную необходимость, лежит субъективное решение. Основание самой объективной науки в мире — субъективно.
Так мы приходим к фундаментальному противоречию аксиоматического метода, которое он не может разрешить, не признав собственного поражения.
С одной стороны, аксиоматический метод требует исключения субъекта из процесса доказательства. Доказательство должно быть формальным, механическим, проверяемым автоматом.
С другой стороны, аксиоматический метод не может обосновать собственные аксиомы без субъекта. Выбор аксиом — это всегда акт интуиции, веры, философского предпочтения. Это человеческое, слишком человеческое действие.
Математики решили эту проблему простым способом: они о ней забыли. Они договорились, что ZFC — это стандарт, и перестали спрашивать, почему. Они сделали вид, что выбор аксиом — это технический вопрос, решённый раз и навсегда. Субъект, изгнанный из парадной двери, пролез через чёрный ход — и они заперли чёрный ход на замок, а ключ выбросили.
Но проблема никуда не делась. Она просто перешла в хроническую форму. P vs NP — это и есть тот самый вопрос, который аксиоматический метод не может решить, потому что он требует от системы осознать собственные основания. А система, исключившая субъекта, на это не способна.
2.3. Родо-видовые определения как единственный язык математики
Если аксиоматический метод — это логистика бессубъектной математики, то родо-видовые определения — это её единственный язык. Математики не просто изгнали субъекта. Они переписали словарь так, чтобы субъекту в нём просто не нашлось грамматической роли.
Аристотель, который, как мы помним, пытался предупредить человечество об опасностях актуальной бесконечности, подарил логике и ещё один инструмент — теорию определения через ближайший род и видовое отличие [47]. Идея проста и изящна. Чтобы определить понятие, вы указываете, к какому более широкому классу (роду) оно принадлежит, а затем называете признак (видовое отличие), который выделяет его среди всех остальных элементов этого класса.
«Человек есть животное (род), обладающее разумом (видовое отличие)». «Квадрат есть прямоугольник (род), у которого все стороны равны (видовое отличие)». Логическая машина работает безупречно: вы берёте готовый, уже существующий класс объектов, и отсекаете от него лишнее, пока не останется ровно то, что вам нужно.
Этот метод идеально подходит для таксономии — наведения порядка в уже существующей куче. Ботаник, классифицирующий растения, или библиотекарь, расставляющий книги по полкам, — вот прообраз мыслителя, вооружённого родо-видовым методом. Он не создаёт новые виды. Он раскладывает по ящикам то, что уже есть.
Математика, особенно после Кантора и торжества теории множеств, превратилась в гигантскую, необозримую библиотеку платоновских объектов. Каждый математический объект — число, функция, пространство, группа — это не процесс, не конструкция, не действие, а готовая вещь, которая лежит на определённой полке и ждёт, пока её оттуда достанут.
А раз все объекты уже существуют в платоновском мире, то единственная задача математика — правильно их классифицировать. Указать их род, указать их видовое отличие — и готово. Определение состоялось.
Возьмём любое современное математическое определение. «Группа — это множество (род), на котором задана ассоциативная бинарная операция, существует нейтральный элемент, и для каждого элемента существует обратный (видовые отличия)». «Топологическое пространство — это множество (род) с выделенной системой подмножеств, замкнутой относительно конечных пересечений и произвольных объединений (видовые отличия)». «Гамильтонов цикл — это подграф (род), в котором каждая вершина имеет степень ровно два и который является связным (видовые отличия)» [19].
Общий шаблон до тошноты предсказуем. Берётся некоторое множество-род, и на него навешиваются условия-отличия. Чем сложнее объект, тем длиннее список отличий. Но суть не меняется: определить — значит отсечь лишнее от уже существующего.
Торжество родо-видового метода было настолько полным, что математики перестали замечать, что они потеряли вместе с альтернативами. А потеряли они, ни много ни мало, саму возможность говорить о процессе.
Посмотрим на два определения.
Эйлеров цикл (родо-видовое определение): Подграф, в котором каждая вершина имеет чётную степень. Всё. Объект определён, его свойства заданы, его можно искать или проверять.
Эйлеров цикл (конструктивное определение): Начни с любой вершины. Иди по непройденным рёбрам, пока можешь. Если вернулся в начало и остались непройденные рёбра — начни новый цикл из вершины, у которой есть непройденные рёбра, и вклей его в уже построенный. Повторяй, пока все рёбра не будут пройдены [48].
Первое определение говорит: «Вот что такое эйлеров цикл». Второе говорит: «Вот как его сделать». Первое классифицирует. Второе порождает. Первое не требует субъекта — объект просто есть или нет. Второе требует субъекта — того, кто начинает, идёт, возвращается, вклеивает.
Математика выбрала первое и забыла второе. Точнее, она сослала второе на кухню, в область «алгоритмов» и «приложений», объявив его не настоящей математикой, а так, инженерной поделкой. Настоящая математика — это та, где определения через род и вид. Где объекты просто есть, а не становятся.