Пять задач современности, которые еще не решены

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

Фото: Helloquence / Unsplash

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

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

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

Гипотеза формулируется следующим образом: если Ax+By=Cz, где 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 минут. Но, к сожалению, это всего лишь частный случай. Сейчас есть несколько десятков алгоритмов, но среди них нет ни одного универсального.

https://42.tut.by/660068