Тайны цифр: погружение в мир нерешенных задач математики. Часть 2

1. P против NP

Диаграмма Эйлера для P, NP, NP-полных и NP-трудных наборов задач теории вычислений

Проблема P и NP связана с классификацией вычислительных задач на основе присущей им сложности. Другими словами, возникает вопрос: может ли каждая проблема, предлагаемое решение которой может быть эффективно проверено компьютером за полиномиальное время (время выполнения алгоритма растет медленно или линейно по сравнению с увеличением размера входных данных), также эффективно решена с помощью компьютера за полиномиальное время?

Задача P vs NP в теории вычислений заключается в выяснении, можно ли быстро (эффективно) решить каждую задачу, для которой можно быстро проверить правильность решения. Если это возможно, то говорят, что P (класс задач, решаемых эффективно) равно NP (класс задач, для которых решение можно быстро проверить). Если же некоторые задачи из NP нельзя эффективно решить, то P не равно NP. Также существует класс задач NP-полный (NP-complete), который включает самые сложные задачи из NP, и если хотя бы одну из них можно решить быстро, то все задачи из NP можно решать быстро.

В теории вычислений существует три класса сложности: P, NP и NP-полный.

P (полиномиальное время) представляет собой класс сложности задач, которые можно решить с помощью детерминированных машин Тьюринга в разумные сроки. Это эффективно, потому что время поиска решений растет с управляемой полиномиальной скоростью по мере увеличения сложности входных данных.

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

NP-полные задачи представляют собой подмножество NP-задач. Это одни из самых сложных проблем в NP, поскольку считается, что они не находятся ни явно в P, ни явно вне его. Если для любой NP-полной задачи можно найти алгоритм с полиномиальным временем, это будет означать, что P = NP, что позволит решить один из наиболее важных вопросов информатики.

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

P vs NP – одна из семи задач, удостоенных Премии тысячелетия Института математики Клэя, за решение которой предлагается денежная премия в 1 миллион долларов, что подчеркивает ее огромное значение в математике и информатике.

2. Существование матриц Адамара определенных порядков

Граф Адамара, основанный на матрице Адамара

Матрица Адамара — это квадратная матрица с элементами +1 или -1, названная в честь французского математика Жака Адамара. Каждая строка матрицы Адамара представляет собой взаимно ортогональный вектор, то есть эти строки математически перпендикулярны. Свойства матрицы подразумевают, что те же характеристики справедливы и для ее столбцов.

Матрица Адамара – это квадратная матрица, элементы которой состоят только из −1−1 и +1+1. Она имеет интересное свойство: строки и столбцы матрицы попарно ортогональны. Это значит, что скалярное произведение любых двух разных строк (или столбцов) равно нулю.

Если мы возьмем первую строку [+1,+1] и вторую строку [+1,−1], их скалярное произведение будет равно нулю: (+1)⋅(+1)+(+1)⋅(−1)=1−1=0(+1)⋅(+1)+(+1)⋅(−1)=1−1=0

Существование матриц Адамара определенного порядка (количества строк и столбцов) является давней математической проблемой. Гипотеза Адамара ставит вопрос о том, существует ли матрица Адамара порядка 4k для каждого положительного целого числа k, что остается нерешенной проблемой.

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

В сфере квантовых вычислений матрицы Адамара играют жизненно важную роль, особенно при построении квантовых гейтов Адамара и преобразований Адамара для квантовых алгоритмов. Различные конструкции, например Методы Сильвестра и Пейли позволили получить матрицы Адамара разных порядков. Конструкция Сильвестра приводит к матрицам порядка 1, 2, 4, 8 и так далее.

Конструкция Пейли, представленная Раймондом Пейли, еще больше расширила доступные представления. Однако все еще существуют порядки, для которых матрица Адамара неизвестна, например порядки 668, 716, 892 и другие.

3. Проблема Лемера

Делители составного числа 10

Проблема Лемера – это математический вопрос, который спрашивает, может ли существовать составное число n с определенным свойством, связанным с тотент-функцией Эйлера. Тотент-функция Эйлера, обозначаемая как φ(n), вычисляет количество натуральных чисел меньше n, которые взаимно просты (не имеют общих делителей, кроме 1) с n. Примечательно, что φ(n) равно n-1 только тогда, когда n — простое число.

Лемер предположил, что никакие составные числа не обладают особым свойством, связанным с φ(n). Проще говоря, проблема Лемера спрашивает, существуют ли непростые числа, для которых определенная математическая функция (φ(n)) дает определенное значение: n-1.

Математик Д. Х. Лемер впервые предложил эту головоломку в 1932 году. Ранние работы Лемера в этой области показали, что, если составное решение n существует, оно должно соответствовать определенным критериям: нечетное, свободное от квадратов и делящееся как минимум на 7 различных простых чисел.

Примечательно, что сам Лемер определил, что любое составное решение должно быть числом Кармайкла. Число Кармайкла — это особый вид составного числа, которое ведет себя как простое число, когда дело касается определенных математических свойств.

Кроме того, тщательные исследования Коэна, Хагиса и других математиков установили строгие условия для потенциальных решений, указывая на необходимость огромных значений n и большого количества различных простых делителей.

4. Проблема развязывания узлов

Узелок, описанный Морвен Тистлтуэйт

Проблема развязывания узла в математике заключается в том, чтобы алгоритмически определить, можно ли превратить узел в простой круг без завязок. Поиск решения проблемы распутывания узлов является частью понимания внутренней сложности решения вычислительных задач (или количества ресурсов, необходимых для решения проблемы).

Ранние попытки понять сложность проблемы развязывания включали ее классификацию по различным классам сложности. В 1999 году Хасс, Лагариас и Пиппенджер добились значительного прогресса, продемонстрировав, что проблема развязывания принадлежит классу сложности NP (класс задач, для которых решение можно быстро проверить).

Однако поиски решения продолжались. В 2014 году Грег Куперберг в предположении обобщенной гипотезы Римана также показал, что проблема развязывания принадлежит к задачам NP. Это означало, что можно эффективно проверить незавязанное состояние узла.

Сложность проблемы развязывания связана с областью топологии и геометрических представлений узлов. Для решения проблемы были предложены различные алгоритмы, некоторые из которых основаны на теории нормальных поверхностей Хакена (Многообразие Хакена). Несмотря на значительный прогресс, понимание точной вычислительной сложности проблемы развязывания остается активной областью исследований.

5. Задача Эйлера о кирпиче

Кирпич Эйлера с ребрами a, c, b и диагоналями грани d, e, f

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

а² + b² = d²

а² + с² = е²

b² + c² = f²

В этой системе «a», «b» и «c» представляют длины ребер кубоида, а «d», «e» и «f» соответствуют длинам диагоналей грани.

Задача состоит в том, чтобы найти идеальный кирпич Эйлера, то есть диагональ пространства имеет целую длину. Другими словами:

a² + b² + c² = g²

Здесь g — диагональ пространства.

Новаторская работа Эйлера привела к исследованию таких кубоидов. Сам Эйлер нашел параметрические решения проблемы, однако решения не охватывают все возможные случаи. Поиск идеального кирпича Эйлера оставался нерешенной проблемой на протяжении веков, несмотря на обширные математические исследования и компьютерные поиски.

6. Гипотеза Бёрча — Свиннертон-Дайера

Эллипс (красный) как коническое сечение

Гипотеза Бёрча — Свиннертон-Дайера — это математическая гипотеза, которая обращается к рациональным решениям уравнений, определяющих эллиптическую кривую.

Гипотеза стремится установить связь между арифметическими свойствами эллиптической кривой и поведением функции, называемой L-функцией. Основная идея гипотезы заключается в том, что, если мы поймем эту связь, мы сможем выяснить, сколько рациональных точек существует на этих эллиптических кривых. Доказательство гипотезы даст понимание эллиптических кривых, простых чисел и криптографии.

В начале 1960-х годов два математика, Брайан Джон Бёрч и Питер Суиннертон-Дайер, начали задумываться над этой проблемой. Они использовали компьютеры и сделали несколько интересных наблюдений.

Математики заметили, что количество точек следует определенной закономерности, когда вы смотрите на эллипсы определенным образом. Гипотеза доказана для конкретных случаев, но общее доказательство не установлено. Гипотеза Бёрча и Суиннертона-Дайера – одна из семи задач Премии тысячелетия Математического института Клея с наградой в 1 миллион долларов.

7. Уравнения Навье-Стокса

Течение жидкости вокруг твердой сферы, моделируемое уравнениями Навье-Стокса

Уравнения Навье-Стокса представляют собой систему дифференциальных уравнений в частных производных, описывающих динамику вязких жидких материалов. Уравнения выражают баланс импульса и сохранения массы для ньютоновских жидкостей (воды, воздуха и т. д.), учитывая такие факторы, как вязкость.

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

Проще говоря, вопрос спрашивает, всегда ли мы можем найти решение, которое описывает поведение жидкости непрерывным и плавным образом без каких-либо резких изменений или сингулярностей.

Уравнения разрабатывались в течение нескольких десятилетий: вклад Клода-Луи Навье начался в 1822 году, а работы Джорджа Габриэля Стоукса — с 1842 по 1850 год.

Уравнения привлекли большое внимание благодаря своей полезности в прогнозировании погодных условий, моделировании течений в океане, понимании течения жидкости в трубопроводах и воздуха вокруг крыльев самолетов, а также моделировании поведения кровотока в системе кровообращения человека. Несмотря на обширные усилия, остается проблема точного решения в трех измерениях. Это одна из семи задач Премии тысячелетия с наградой в 1 один миллион долларов.

Заключение

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

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