Невирішені математичні задачі сучасності

Невирішені задачі математики

Гіпотеза про близнюків: простих чисел-близнюків нескінченно багато

Гіпотеза Гольдбаха (1742)

ГІПОТЕЗА КОЛЛАТЦА

1. Якщо число парне, розділіть його на 2.
2. Якщо ж непарне, помножте його на 3 і додайте 1.
3. Повторіть крок 1 із отриманим числом.

Які правильні n-кутники можна побудувати циркулем і лінійкою?

Просте число Ферма — це просте число виду: $${2^{2^n} + 1}$$ На 2021 рік єдиними відомими простими числами Ферма є $$F_{0}=3, F_{1}=5, F_{2}=17, F_{3}=257, F_{4}=65537.$$
Ми знайдемо відповідь на питання про можливість побудови правильних n-кутників циркулем і лінійкою для будь-якого n в той же момент, як тільки знайдемо відповідь на питання про існування простих чисел Ферма.

Задача про пакування куль

Задача про пакування куль — задача комбінаторної геометрії про розміщення однакових куль в евклідовому просторі без їх взаємного перетинання. Типова постановка задачі наступна: знайти спосіб розташування куль в просторі, за якого кулі займають найбільшу частину цього простору.

Історія задачі

В кінці 1500-х років сер Волтер Рейлі попросив англійського математика Томаса Герріота придумати ефективний спосіб укладання гарматних ядер на кораблях британського військового флоту. Герріот розповів про це завдання астроному Йогану Кеплеру. Кеплер припустив, що найбільш щільний спосіб упаковки сфер вже і так застосовується — при укладанні гарматних ядер і фруктів: перший шар викладається кулями поруч одна з одною у вигляді шестикутника, другий в заглиблення на стиках куль нижнього шару і т.д. У великій тарі при такому варіанті укладання максимальна щільність буде близько 74%: \[{\displaystyle {\frac {\pi }{3{\sqrt {2}}}}\simeq 0.74048}\] Кеплер вважав, що це найщільніший варіант упаковки, але не зміг цього довести. В 1694 році дискусію щодо пакування куль продовжили Девід Грегорі та Ісаак Ньютон в Кембриджі. Гіпотеза Кеплера залишилася недоведеною і потрапила до списку з 23 невирішених математичних задач, складеного у 1900 році Давидом Гільбертом. В 1998 році математик Томас Гейлс запропонував складне доведення цієї гіпотези, що базувалось на простому переборі всіх можливих варіантів (варіанти обчислювались за допомогою комп'ютера), але доведення не є математично обґрунтованим. Гіпотеза Кеплера є найпростішим випадком узагальненої задачі про пакування куль

Класи P і NP

Відповідь на питання про рівність класів P і NP визначила б, чи дійсно завдання легше перевірити, ніж вирішити (P ≠ NP). Або вирішити настільки ж просто, як і перевірити (P = NP).

З визначення класів P і NP відразу випливає наслідок: \({\displaystyle P\subseteq NP}\). Проте досі не відомо про строгість цього включення, тобто чи існує алгоритм, який лежить в NP, але не лежить в P. Якщо такого алгоритму не існує, то всі завдання, що належать класу NP, можна буде вирішувати за поліноміальний час. Зараз найскладніші NP-задачі (так звані NP-повні задачі) можна вирішити за експоненційний час, що майже завжди є неприйнятним. Вперше питання про рівність класів було поставлено Куком і Левіним у 1971 р. На сьогодні більшість математиків вважають, що ці класи не рівні, а дехто думає, що гіпотеза не виводиться з поточної системи аксіом, отже не може бути доведена або спростована. Зараз проблема рівності класів P і NP є однією із семи проблем тисячоліття, за вирішення якої Математичний інститут Клея призначив премію в мільйон доларів США.

Тест простоти довільного числа n належить класу P (2004 рік)

Кажуть, що завдання знаходиться в P, якщо існує швидкий алгоритм, який може вирішити задачу. Алгоритм називається швидким (алгоритм із поліноміальним часом), якщо він вирішує задачу за f(x) кроків, де f — поліноміальна функція.

ПОЛІНОМІАЛЬНА ФУНКЦІЯ це узагальнення поняття цілої раціональної функції \({\displaystyle f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\dotsb +a_{2}x^{2}+a_{1}x+a_{0}=\sum _{i=0}^{n}a_{i}x^{i},}\) де n∈N, \({\displaystyle a_{n},a_{n-1},\ldots ,a_{2},a_{1},a_{0}\in \mathbb {R} } \) і \({\displaystyle a_{n}\neq 0}.\)

Протягом 400 років математики намагалися з'ясувати, чи можна вирішити задачу визначення простоти числа за поліноміальний час. Виявляється, що так.

Тест Агравала - Каяла - Саксени

Якщо існує \({\displaystyle r\in \mathbb {Z} }\) таке, що \({\displaystyle o_{r}(n)>\log ^{2}n} \) і для довільного a від 1 до \({\displaystyle \left\lfloor {\sqrt {\varphi (r)}}\log(n)\right\rfloor }\) виконується порівняння \({\displaystyle (x+a)^{n}\equiv (x^{n}+a){\pmod {x^{r}-1,\;n}}}\), то n — або просте число, або степінь простого числа.

Більш складні задачі, які потребують вирішення

Гіпотеза Рімана

Теорія Янга — Мілса