Пять нерешенных математических задач

Источник материала:

Мы ранее рассказывали про шесть «задач тысячелетия», за решение которых заплатят миллион долларов. Но помимо этих заданий существуют еще множество других, которые все еще ждут своего доказательства (или опровержения). 42.TUT.BY рассказывает про пять математических задач, которые не так просты, как кажутся.

Гипотеза Била

Гипотеза Била — гипотеза в теории чисел, обобщение великой теоремы Ферма. Она была предложена в 1993 году техасским миллиардером и математиком-любителем Эндрю Билом, который учредил премию за ее доказательство или опровержение в 100 тысяч долларов.

Американское математическое общество в 2013-м объявило о повышении награды до 1 миллиона долларов.

Гипотеза формулируется следующим образом: если A^x+B^y=C^z, где A, B, C, x, y, z- натуральные числа и x, y, z > 2, то A, B, C имеют общий простой делитель. Хитрость в том, что доказательство гипотезы Била означает, что Великая теорема Ферма может быть доказана от противного. А над таким элегантным доказательством математики бьются с 1637 года.

Гипотеза о числах-близнецах

Числа-близнецы — это пары простых чисел, отличающихся на 2. Например, 3 и 5 либо 881 и 883. Все пары чисел-близнецов (кроме 3 и 5), имеют вид 6n±1, так как числа с другими вычетами по модулю 6 делятся на 2 или на 3.

Предполагается, что таких пар бесконечно много, но это не доказано. Так, в 2013 году было объявлено о доказательстве, что существует бесконечно много пар простых чисел, которые отличаются не более чем на 70 миллионов. Спустя пару месяцев было объявлено о снижении оценки уже до 59 470 640, а затем, буквально через несколько дней — что граница может быть уменьшена до 4 982 086.

Сейчас существуют теоретические обоснования бесконечности пар чисел-близнецов с разницей в 12 и 6, но доказанной является лишь разница в 246. Этот результат был достигнут в апреле 2014 года Пэйсом Нильсеном из университета Брайгама Янга в Юте.

На данный момент, наибольшими известными простыми-близнецами являются числа 2003663613⋅2195000±1. Они были найдены в сентябре 2016 года в рамках проекта добровольных вычислений PrimeGrid.

Проблема Гольдбаха (бинарная)

Проблема Гольдбаха — это утверждение о том, что любое четное число, начиная с 4, можно представить в виде суммы двух простых чисел. Эта математическая проблема была включена вместе с гипотезой Римана в список проблем Гильберта.

Проблема была сформулирована математиком Кристианом Гольдбахом в переписке с Леонардом Эйлером в 1742 году. Гольдбах тогда написал, что «каждое нечетное число, большее 5, можно представить в виде суммы трех простых чисел». В ответ Эйлер выдвинул более сильную гипотезу: «Каждое четное число, большее двух, можно представить в виде суммы двух простых чисел». Первое утверждение теперь называется тернарной проблемой Гольдбаха, второе — бинарной проблемой Гольдбаха (или проблемой Эйлера).

В 2013 году тернарная гипотеза Гольдбаха была окончательно доказана перуанским Харальдом Гельфготтом. Но вот бинарная проблема по-прежнему далека от решения.

Гипотеза Коллатца

Гипотеза Коллатца получила широкую известность благодаря простоте формулировки. Она получила свое название по имени немецкого математика Лотара Коллатца, сформулировавшего эту задачу 1 июля 1932 года.

Ее еще называют «гипотеза 3n+1», «сиракузская проблема» и «числа-градины». В чем суть? Рассмотрим идею на примере последовательности чисел, называемой сиракузской последовательностью.

Берем любое натуральное число n: если оно четное, то делим его на 2, а если нечетное, то умножаем на 3 и прибавляем 1 (то есть, 3n+1). Над полученным числом выполняем те же самые действия, и так далее. Гипотеза заключается в том, что какое бы начальное число n мы ни взяли, то рано или поздно получим единицу.

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

В августе 2009 года на платформе BOINC был запущен проект добровольных распределенных вычислений «Collatz Conjecture», который должен проверять гипотезы Коллатца на больших числах. Позже к нему присоединился и проект распределенных вычислений yoyo@Home.

По состоянию на апрель 2019 года были проверены все натуральные числа меньше чем 1 152 921 504 606 846 976, и каждое из них за конечное количество шагов соответствовало условиям гипотезы. Но это, разумеется, не конец.

Задача развязывания

Еще одна обманчиво простая задача. Идея в том, чтобы вычислить минимальное время, необходимое, чтобы развязать узел.

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

Классом P называют множество задач, которые компьютер может решить «быстро», то есть, за полиномиальное время. К ним относят базовые арифметические действия, сортировку списков, поиск по таблице с данными.

Найти алгоритм развязывания вполне возможно, но сколько это потребует ресурсов? Может, это задание окажется не по зубам даже самому мощному компьютеру?

В 2011 году американский математик Грег Куперберг доказал, что задача развязывания принадлежит классу co-NP, и сократил время развязывания узла из 139 вершин со 108 часов до 10 минут. Но, к сожалению, это всего лишь частный случай. Сейчас есть несколько десятков алгоритмов, но среди них нет ни одного универсального.