Иногда опасна не сама задача, а то, какие инструменты мы создаем, пытаясь ее решить.
В первой части мы познакомились с семью математическими загадками, которые мучают ученых десятилетиями, а то и столетиями. Но это лишь половина истории. Математика — безграничная вселенная нерешенных вопросов, и сегодня мы продолжим наше путешествие по самым интригующим из них.
Если первая семерка была в основном про числа — простые, совершенные, трансцендентные, — то теперь расширим горизонты. Впереди вычислительная сложность, загадки геометрии, топологические головоломки и уравнения, описывающие течение жидкостей. Некоторые из этих задач обещают миллион долларов от Института Клэя, другие просто бросают вызов человеческому разуму. Но все они объединены одним: простая формулировка и дьявольская сложность решения.
Готовы? Тогда приступим ко второй порции математических орешков, которые пока никому не по зубам.
1. P против NP — вопрос на миллион долларов
Цифровой контроль неизбежен.
Диаграмма Эйлера для P, NP, NP-полных и NP-трудных задач в теории вычислений
Представьте, что вам дали судоку 9×9. Проверить, правильно ли решена головоломка, можно за пару минут — просто убедитесь, что в каждой строке, столбце и квадрате 3×3 все цифры от 1 до 9 встречаются ровно по одному разу. А вот решить ее с нуля может занять час, а то и больше. Вопрос "P против NP" спрашивает: так ли это всегда? Может ли оказаться, что любую задачу, которую легко проверить, можно и легко решить?
В теории вычислений существуют классы сложности. Класс P (полиномиальное время) — это задачи, которые компьютер может решить быстро. Здесь "быстро" означает, что время работы алгоритма растет как полином от размера входных данных: если данных стало в два раза больше, времени нужно, скажем, в четыре раза больше, а не в миллион раз. Сортировка списка, поиск кратчайшего пути в графе — типичные представители класса P.
Класс NP (недетерминированное полиномиальное время) — это задачи, для которых готовое решение можно быстро проверить. Судоку, задача коммивояжера, раскладка рюкзака — все они в NP. У вас есть предполагаемый ответ? Отлично, компьютер за разумное время скажет, верен он или нет. Но найти этот ответ с нуля может быть чудовищно сложно.
Очевидно, что P ⊆ NP: если задачу легко решить, то решение легко и проверить. Вопрос в том, равны ли эти классы. Если P = NP, то для каждой задачи из NP существует быстрый алгоритм решения. Это перевернуло бы криптографию (большинство шифров основаны на сложности задач из NP), оптимизацию, искусственный интеллект — да и весь современный мир информационных технологий.
Существует подкласс задач NP, называемый NP-полными задачами. Это самые "трудные" задачи в NP: если хотя бы для одной из них найдется быстрый алгоритм, значит, P = NP, и все задачи из NP можно решать быстро. Первую NP-полную задачу — выполнимость булевых формул (SAT) — обнаружил Стивен Кук в 1971 году. С тех пор найдены тысячи NP-полных задач во всех областях науки и техники.
Большинство специалистов считают, что P ≠ NP. Интуиция подсказывает: проверка проще, чем поиск. Но доказательства нет. Проблема P против NP входит в семь "Задач тысячелетия" Института Клэя с призом в миллион долларов. В 2025 году появляются работы с попытками решения, но пока ни одна не получила признания математического сообщества. Как заметил математик Скотт Ааронсон, "доказывать P ≠ NP трудно именно потому, что мы пытаемся доказать, что чего-то не существует — эффективного алгоритма для всех задач NP".
2. Матрицы Адамара — геометрия ортогональности
Граф Адамара, основанный на матрице Адамара
Матрица Адамара — квадратная таблица, заполненная только единицами и минус единицами, причем строки (и столбцы) попарно ортогональны. Это значит, что если взять любые две разные строки, умножить их элементы попарно и сложить результаты, получится ноль. Названа в честь французского математика Жака Адамара, который в 1893 году доказал, что такие матрицы имеют максимально возможный определитель среди всех матриц с элементами, не превышающими по модулю единицы.
Простейший пример — матрица 2×2 с элементами [+1, +1] и [+1, −1]. Проверим ортогональность: (+1)·(+1) + (+1)·(−1) = 1 − 1 = 0. Отлично. Дальше можно строить матрицы порядков 4, 8, 16 с помощью конструкции Сильвестра, которая удваивает размер: берем матрицу H и собираем блочную матрицу [[H, H], [H, −H]]. Получается новая матрица Адамара вдвое большего порядка.
Математики быстро обнаружили, что матрицы Адамара существуют только для порядков, кратных четырем (за исключением порядков 1 и 2). Гипотеза Адамара утверждает: для любого n, кратного 4, существует матрица Адамара порядка n. Звучит правдоподобно, но доказательства нет уже больше столетия.
Более того, известно несколько конструкций для различных порядков. Метод Сильвестра дает матрицы порядков 2^k. Конструкция Пейли, предложенная в 1933 году, использует квадратичные вычеты и работает для порядков p+1, где p — простое число определенного вида. Существуют и другие методы, но ни один не покрывает все случаи.
На 2025 год наименьшие порядки, для которых матрица Адамара не найдена: 668, 716, 892, и далее несколько десятков случаев до тысячи. Каждый год математики находят матрицы для нескольких новых порядков, но общего доказательства гипотезы все нет. Интересно, что матрицы Адамара находят применение в квантовых вычислениях (квантовый гейт Адамара), теории кодирования, обработке сигналов и даже в спектрометрии.
3. Проблема Лемера — загадочная функция φ(n)
Делители составного числа 10
Функция Эйлера φ(n) — одна из базовых функций в теории чисел, и при этом невероятно практичная. Именно на ней построен алгоритм RSA — основа современного интернет-шифрования. Каждый раз, когда вы видите замочек в адресной строке браузера, функция Эйлера работает в фоновом режиме, защищая ваши данные. Но у нее есть и теоретические загадки.
Функция φ(n) показывает, сколько чисел от 1 до n-1 взаимно просты с n (не имеют с ним общих делителей, кроме единицы). Например, φ(10) = 4, потому что среди чисел 1, 2, 3, 4, 5, 6, 7, 8, 9 только четыре (1, 3, 7, 9) не делятся ни на 2, ни на 5.
Для простых чисел все просто: φ(p) = p−1, потому что все числа от 1 до p−1 взаимно просты с простым p. А вот для составных чисел значение φ(n) всегда строго меньше n−1. Всегда ли? В 1932 году математик Деррик Лемер задался вопросом: может ли существовать составное число n, для которого φ(n) делит n−1?
Если такое число существует, оно должно обладать рядом экзотических свойств. Лемер показал, что оно обязательно нечетное, свободное от квадратов (ни один простой делитель не входит в него дважды) и имеет минимум семь различных простых делителей. Более того, такое число должно быть числом Кармайкла — составным числом, которое ведет себя как простое в некоторых тестах на простоту.
Числа Кармайкла — сами по себе интересный объект. Наименьшее из них — 561 = 3×11×17. Долгое время не знали, конечно ли их количество, но в 1994 году было доказано, что чисел Кармайкла бесконечно много. Однако среди всех этих чисел ни одно не удовлетворяет условию Лемера.
Дальнейшие исследования Коэна, Хагиса и других математиков установили еще более жесткие ограничения. Если решение проблемы Лемера существует, это чудовищно большое число с огромным количеством простых делителей. Но доказательства несуществования такого числа нет, и проблема остается открытой уже почти столетие.
4. Проблема развязывания узлов — топология завязок
Узел, описанный Морвеном Тистлтуэйтом
Возьмите веревку, завяжите узел и склейте концы. Теперь вопрос: можно ли этот узел развязать, не разрезая веревку и не разрывая ее? В математической постановке: можно ли непрерывными деформациями (без разрезов и склеиваний) превратить данную замкнутую кривую в обычный круг?
Это классическая проблема топологии — раздела математики, изучающего свойства фигур, которые сохраняются при непрерывных преобразованиях. Для человека очевидно, что простой круг развязан, а трилистник завязан. Но как это доказать формально? И главное — как алгоритмически определить для произвольного узла, развязан он или нет?
Долгое время не было понятно, к какому классу сложности относится эта задача. В 1999 году Хасс, Лагариас и Пиппенджер доказали, что проблема принадлежит классу NP: если узел можно развязать, то существует последовательность деформаций полиномиальной длины, которая это продемонстрирует, и эту последовательность можно эффективно проверить.
Но принадлежит ли проблема классу P? То есть, существует ли быстрый алгоритм, который всегда определит, развязан ли узел? Были предложены различные подходы на основе теории нормальных поверхностей Хакена, инвариантов узлов и других методов алгебраической топологии. В 2014 году Грег Куперберг показал (при условии обобщенной гипотезы Римана), что задача также находится в co-NP — классе задач, где можно быстро проверить, что решения не существует (своего рода зеркальное отражение NP).
Практические алгоритмы для развязывания узлов существуют и успешно работают на большинстве реальных примеров. Но точная вычислительная сложность задачи остается открытым вопросом. Возможно, это одна из немногих естественных задач в NP ∩ co-NP, не лежащих в P.
5. Задача Эйлера о кирпиче — идеальный параллелепипед
Кирпич Эйлера с ребрами a, b, c и диагоналями граней d, e, f
Возьмите прямоугольный параллелепипед — обычный "кирпич". У него три ребра (назовем их a, b и c) и три диагонали граней (d, e и f). Кирпич Эйлера — это такой параллелепипед, у которого все эти шесть величин — целые числа.
По теореме Пифагора: a² + b² = d², a² + c² = e², b² + c² = f². Это система диофантовых уравнений — уравнений, где требуются целочисленные решения. Эйлер нашел параметрические решения этой системы, и сейчас известны тысячи кирпичей Эйлера. Наименьший пример: (a, b, c) = (44, 117, 240), диагонали граней (125, 244, 267).
Но есть еще одна диагональ — пространственная диагональ g, проходящая через весь кирпич. Для нее выполняется a² + b² + c² = g². Вопрос: существует ли идеальный кирпич Эйлера, у которого и пространственная диагональ тоже целая?
Несмотря на активные компьютерные поиски, идеальный кирпич так и не найден. Проверены все возможности до астрономических размеров. При этом доказательства несуществования тоже нет. Задача выглядит обманчиво простой — всего четыре уравнения с четырьмя неизвестными — но сопротивляется решению уже больше двух столетий.
Интересно, что существуют "почти идеальные" кирпичи, где все величины целые, кроме одной из диагоналей грани. Существуют также идеальные параллелограммы в четырех измерениях. Но трехмерный идеальный кирпич остается неуловимым.
6. Гипотеза Бёрча — Свиннертон-Дайера — эллиптические кривые и L-функции
Эллипс (красный) как коническое сечение
Эллиптическая кривая — это вовсе не эллипс, как можно подумать из названия. Это множество точек, удовлетворяющих уравнению вида y² = x³ + ax + b. График такого уравнения выглядит как замысловатая кривая с одной или двумя "горбинками". Эллиптические кривые играют центральную роль в современной теории чисел и криптографии.
Один из главных вопросов: сколько рациональных точек (точек с рациональными координатами) лежит на данной эллиптической кривой? Может быть конечное число, может быть бесконечно много. Как это определить, не перебирая все возможности вручную?
В начале 1960-х годов Брайан Бёрч и Питер Свиннертон-Дайер начали изучать эту проблему с помощью компьютера в Кембридже. Они заметили удивительную закономерность: количество рациональных точек связано с поведением определенной аналитической функции — L-функции эллиптической кривой — в точке s = 1.
Гипотеза утверждает: если L-функция обращается в ноль в точке s = 1, то на кривой бесконечно много рациональных точек (и точнее — ранг группы точек положителен). Если L-функция не равна нулю в этой точке, то рациональных точек конечное число (ранг равен нулю). Более сильная версия гипотезы даже предсказывает порядок нуля L-функции — он должен равняться рангу группы точек.
Доказано это только для некоторых частных случаев. Полное доказательство гипотезы Бёрча — Свиннертон-Дайера входит в семь "Задач тысячелетия" с призом в миллион долларов. Решение этой проблемы не только даст ответ на вопрос о рациональных точках на эллиптических кривых, но и откроет новые пути в понимании связей между алгебраической геометрией и аналитической теорией чисел.
7. Уравнения Навье-Стокса — турбулентность и гладкость
Течение жидкости вокруг твердой сферы, моделируемое уравнениями Навье-Стокса
Уравнения Навье-Стокса описывают движение вязких жидкостей — воды, масла, воздуха, крови. Это система дифференциальных уравнений в частных производных, выражающая законы сохранения массы и импульса для любого элемента жидкости. Были сформулированы в XIX веке усилиями Клода-Луи Навье (1822) и Джорджа Габриэля Стокса (1842-1850).
Уравнения используются везде: прогноз погоды, проектирование самолетов и кораблей, моделирование течений в океане, расчет кровотока в сосудах, даже анимация жидкостей в компьютерной графике. Численные методы позволяют находить приближенные решения для практических задач. Но с математической точки зрения остаются фундаментальные вопросы.
Проблема тысячелетия формулируется так: для трехмерного случая, докажите, что решения уравнений Навье-Стокса существуют для всех времен и остаются гладкими (без сингулярностей) при разумных начальных условиях. Или найдите контрпример — начальное условие, при котором решение "взрывается" за конечное время.
Физически вопрос в том, может ли гладкое течение жидкости внезапно развить бесконечную скорость или бесконечный градиент скорости в какой-то точке. Такие сингулярности кажутся нефизичными, но математически их существование не исключено. Численные эксперименты показывают, что течения могут становиться чрезвычайно сложными (турбулентность!), но сингулярности не возникают.
Для двумерного случая проблема решена — доказано существование гладких решений на все времена. А вот трехмерный случай сопротивляется. Это одна из семи "Задач тысячелетия" Института Клэя, и решение принесет не только миллион долларов, но и фундаментальное понимание турбулентности — явления, которое Ричард Фейнман называл "последней великой нерешенной проблемой классической физики".
Взгляд в будущее
Семь задач, описанных здесь вместе с семью из первой части статьи, — это вершины айсберга нерешенных математических проблем. Некоторые из них решатся в ближайшие десятилетия благодаря новым идеям или мощи компьютеров. Другие могут оказаться неразрешимыми в рамках существующей математики — вспомним теоремы Гёделя о неполноте, показавшие, что не все истинные утверждения можно доказать.
Что объединяет эти задачи? Все они возникли из естественных вопросов — о числах, формах, вычислениях, течениях жидкости. Все они просты для понимания, но дьявольски сложны для решения. И все они обещают, что их решение откроет новые горизонты в математике и смежных науках.
История математики полна неожиданностей. Проблема четырех красок (можно ли раскрасить любую карту четырьмя цветами так, чтобы соседние страны имели разные цвета?) казалась простой, но потребовала компьютерной проверки тысяч случаев. Великая теорема Ферма ждала 358 лет и была доказана через связь с эллиптическими кривыми — совершенно неожиданный подход.
Возможно, решающий прорыв в P против NP придет из квантовых вычислений. Может быть, идеальный кирпич Эйлера будет найден завтра с помощью нового алгоритма. А уравнения Навье-Стокса раскроют свои секреты через геометрию или топологию. В математике нет гарантий, есть только азарт поиска и красота открытий.