5 декабря 2014 в 18:54

Задачи тысячелетия. Просто о сложном

• Занимательные задачки ,
• Математика

Привет, хабралюди!

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

После доказательства гипотезы (теперь уже теоремы) Пуанкаре Григорием Перельманом, основным вопросом, который заинтересовал многих, был: «А что же он собственно доказал, объясните на пальцах? » Пользуясь возможностью, попробую объяснить на пальцах и остальные задачи тысячелетия, или по крайней мере подойти в ним с другой более близкой к реальности стороны.

Равенство классов P и NP

Все мы помним из школы квадратные уравнения, которые решаются через дискриминант. Решение этой задачи относится к классу P (P olynomial time) - для нее существует быстрый (здесь и далее под словом «быстрый» подразумевается как выполняющийся за полиномиальное время) алгоритм решения, который и заучивается.

Также существуют NP -задачи (N on-deterministic P olynomial time) , найденное решение которых можно быстро проверить по определенному алгоритму. Для примера проверка методом перебора компьютером. Если вернуться к решению квадратного уравнения, то мы увидим, что в данном примере существующий алгоритм решения проверяется так же легко и быстро как и решается. Из этого напрашивается логичный вывод, что данная задача относится как к одному классу так и ко второму.

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

На просторах интернета также встретил такую интересную и прозрачную формулировку:

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

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

Данная проблема имеет большое значение для самых различных областей знаний, но решить ее не могут уже более 40 лет.

Гипотеза Ходжа

В реальности существуют множество как простых так и куда более сложных геометрических объектов. Очевидно, что чем сложнее объект тем более трудоемким становится его изучение. Сейчас учеными придуман и вовсю применяется подход, основная идея которого заключается в том, чтобы вместо самого изучаемого объекта использовать простые «кирпичики» с уже известными свойствами, которые склеиваются между собой и образуют его подобие, да-да, знакомый всем с детства конструктор. Зная свойства «кирпичиков», становится возможным подступиться и к свойствам самого объекта.

Гипотеза Ходжа в данном случае связана с некоторыми свойствами как «кирпичиков» так и объектов.

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

Всем нам еще со школы известны простые числа которые делятся только на себя и на единицу (2,3,5,7,11...) . С давних времен люди пытаются найти закономерность в их размещении, но удача до сих пор так никому и не улыбнулась. В результате ученые применили свои усилия к функции распределения простых чисел, которая показывает количество простых чисел меньше или равных определенного числа. Например для 4 - 2 простых числа, для 10 - уже 4 числа. Гипотеза Римана как раз устанавливает свойства данной функции распределения.

Многие утверждения о вычислительной сложности некоторых целочисленных алгоритмов, доказаны в предположении верности этой гипотезы.

Теория Янга - Миллса

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

На основе теории Янга-Миллса построена стандартная модель физики элементарных частиц в рамках которой был предсказан и не так давно обнаружен нашумевший бозон Хиггса.

Существование и гладкость решений уравнений Навье - Стокса

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

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

Для уравнения x 2 + y 2 = z 2 в свое время еще Эвклид дал полное описание решений, но для более сложных уравнений поиск решений становится чрезвычайно трудным, достаточно вспомнить историю доказательства знаменитой теоремы Ферма, чтобы убедиться в этом.

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

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

Гипотеза Пуанкаре

Думаю если не все, то большинство точно о ней слышали. Чаще всего встречается, в том числе и на центральных СМИ, такая расшифровка как «резиновую ленту натянутую на сферу можно плавно стянуть в точку, а натянутую на бублик - нельзя ». На самом деле эта формулировка справедлива для гипотезы Тёрстона, которая обобщает гипотезу Пуанкаре, и которую в действительности и доказал Перельман.

Частный случай гипотезы Пуанкаре говорит нам о том, что любое трехмерное многообразие без края (вселенная, например) подобно трехмерной сфере. А общий случай переводит это утверждение на объекты любой мерности. Стоит заметить, что бублик, точно так же как вселенная подобна сфере, подобен обычной кофейной кружке.

Заключение

В настоящее время математика ассоциируется с учеными, имеющими странный вид и говорящие о не менее странных вещах. Многие говорят о ее оторванности от реального мира. Многие люди как младшего, так и вполне сознательного возраста говорят, что математика ненужная наука, что после школы/института, она нигде не пригодилась в жизни.

Но на самом деле это не так - математика создавалась как механизм с помощью которого можно описать наш мир, и в частности многие наблюдаемые вещи. Она повсюду, в каждом доме. Как сказал В.О. Ключевский: «Не цветы виноваты, что слепой их не видит».

Наш мир далеко не так прост, как кажется, и математика в соответствии с этим тоже усложняется, совершенствуется, предоставляя все более твердую почву для более глубокого понимания существующей реальности.

Ответ редакции

Профессор Оксфордского, Кембриджского и Эдинбургского университетов, а также лауреат почти десятка престижных премий в области математики Майкл Фрэнсис Атья представил доказательство гипотезы Римана , одной из семи «проблем тысячелетия», которая описывает, как расположены на числовой прямой простые числа.

Доказательство Атьи небольшое, вместе с введением и списком литературы оно занимает пять страниц. Ученый утверждает, что нашел решение гипотезы, анализируя проблемы, связанные с постоянной тонкой структуры, а в качестве инструмента использовал функцию Тодда. Если научное сообщество сочтет доказательство корректным, то за него британец получит $1 млн от Института математики Клея (Clay Mathematics Institute, Кембридж, Массачусетс).

На приз претендуют также другие ученые. В 2015 году о решении гипотезы Римана заявлял профессор математики Опиеми Энох (Opeyemi Enoch) из Нигерии, а в 2016 году свое доказательство гипотезы представил российский математик Игорь Турканов . По словам представителей Института математики, для того чтобы достижение было зафиксировано, его необходимо опубликовать в авторитетном международном журнале с последующим подтверждением доказательства научным сообществом.

В чем суть гипотезы?

Гипотезу еще в 1859 году сформулировал немецкий математик Бернхард Риман . Он определил формулу, так называемую дзета-функцию, для количества простых чисел до заданного предела. Ученый выяснил, что нет никакой закономерности, которая бы описывала, как часто в числовом ряду появляются простые числа, при этом он обнаружил, что количество простых чисел, не превосходящих x , выражается через распределение так называемых «нетривиальных нулей» дзета-функции.

Риман был уверен в правильности выведенной формулы, однако он не мог установить, от какого простого утверждения полностью зависит это распределение. В результате он выдвинул гипотезу, которая заключается в том, что все нетривиальные нули дзета-функции имеют действительную часть, равную ½, и лежат на вертикальной линии Re=0,5 комплексной плоскости.

Доказательство или опровержение гипотезы Римана очень важно для теории распределения простых чисел, говорит аспирант факультета математики Высшей школы экономики Александр Калмынин . «Гипотеза Римана — это утверждение, которое эквивалентно некоторой формуле для количества простых чисел, не превосходящих данное число x . Гипотеза, например, позволяет достаточно быстро и с большой точностью посчитать количество простых чисел, не превосходящих, к примеру, 10 млрд. Это не единственная ценность гипотезы, потому что у нее есть еще целый ряд довольно далеко идущих обобщений, которые известны как обобщенная гипотеза Римана, расширенная гипотеза Римана и большая гипотеза Римана. Они имеют еще большее значение для разных разделов математики, но в первую очередь важность гипотезы определяется теорией простых чисел», — говорит Калмынин.

По словам эксперта, при помощи гипотезы можно решать ряд классических задач теории чисел: задачи Гаусса о квадратичных полях (проблема десятого дискриминанта), задачи Эйлера об удобных числах, гипотезу Виноградова о квадратичных невычетах и т. д. В современной математике данной гипотезой пользуются для доказательства утверждений о простых числах. «Мы сразу предполагаем, что верна какая-то сильная гипотеза типа гипотезы Римана, и смотрим, что получается. Когда у нас это получается, то мы задаемся вопросом: можем ли мы это доказать без предположения гипотезы? И, хотя такое утверждение пока за пределами того, чего мы можем достигнуть, оно работает как маяк. За счет того, что есть такая гипотеза, мы можем смотреть, куда нам двигаться», — говорит Калмынин.

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

Математические физики заявили о продвижении в работе над 150-летней теоремой, за доказательство которой Математический институт Клэя предлагает награду в миллион долларов. Ученые представили оператор, который удовлетворяет гипотезе Гильберта-Пойя, гласящей, что существует дифференциальный оператор, чьи собственные значения в точности соответствуют нетривиальным нулям дзета-функции Римана. Статья опубликована в журнале Physical Review Letters.

Гипотеза Римана - одна из «задач тысячелетия», за доказательство которых американский Математический институт Клэя выдает премии в миллион долларов. Гипотеза Пуанкаре (теорема Пуанкаре-Перельмана), которую доказал наш соотечественник , входила именно в этот список. Гипотеза Римана, сформулированная в 1859 году, гласит, что все нетривиальные нули дзета-функции Римана (то есть значения комплекснозначного аргумента, обращающие функцию в нуль) лежат на прямой ½ + it, то есть их вещественная часть равна ½. Сама дзета-функция возникает во многих разделах математики, например, в теории чисел она связана с количеством простых чисел, меньших заданного.

Теория функций предсказывает, что множество нетривиальных нулей дзета-функции должно быть похоже на множество собственных значений («решений» для матричных уравнений) некоторой другой функции из класса дифференциальных операторов, которые часто используются в физике. Идея о существовании конкретного оператора с такими свойствами получила название гипотезы Гильберта-Пойя, хотя ни тот, ни другой не публиковали работ на эту тему. «Так как публикаций "авторов" на эту тему нет, то формулировка гипотезы меняется в зависимости от интерпретации, - поясняет один из авторов статьи Дорже Броди из лондонского Университета Брунеля. - Однако два пункта должны быть выполнены: а) необходимо найти оператор, чьи собственные значения соответствуют нетривиальным нулям дзета-функции, и б) определить, что собственные значения являются действительными числами. Основной целью нашей работы был пункт а). Для доказательства части б) необходима дальнейшая работа».

Еще одной важной гипотезой в этой области является идея Берри и Китинга, что в случае существования искомого оператора, он будет теоретически соответствовать некоторой квантовой системе с определенными свойствами. «Мы определили условия квантования гамильтониана Берри-Китинга, таким образом, доказывая гипотезу их имени, - добавляет Броди. - Возможно, это разочарует, но полученный гамильтониан, кажется, не соответствует никакой физической системе очевидным образом; по крайней мере, мы не нашли такого соответствия».

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

Привет, хабралюди!

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

После доказательства гипотезы (теперь уже теоремы) Пуанкаре Григорием Перельманом, основным вопросом, который заинтересовал многих, был: «А что же он собственно доказал, объясните на пальцах? » Пользуясь возможностью, попробую объяснить на пальцах и остальные задачи тысячелетия, или по крайней мере подойти в ним с другой более близкой к реальности стороны.

Равенство классов P и NP

Все мы помним из школы квадратные уравнения, которые решаются через дискриминант. Решение этой задачи относится к классу P (P olynomial time) - для нее существует быстрый (здесь и далее под словом «быстрый» подразумевается как выполняющийся за полиномиальное время) алгоритм решения, который и заучивается.

Также существуют NP -задачи (N on-deterministic P olynomial time) , найденное решение которых можно быстро проверить по определенному алгоритму. Для примера проверка методом перебора компьютером. Если вернуться к решению квадратного уравнения, то мы увидим, что в данном примере существующий алгоритм решения проверяется так же легко и быстро как и решается. Из этого напрашивается логичный вывод, что данная задача относится как к одному классу так и ко второму.

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

На просторах интернета также встретил такую интересную и прозрачную формулировку:

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

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

Данная проблема имеет большое значение для самых различных областей знаний, но решить ее не могут уже более 40 лет.

Гипотеза Ходжа

В реальности существуют множество как простых так и куда более сложных геометрических объектов. Очевидно, что чем сложнее объект тем более трудоемким становится его изучение. Сейчас учеными придуман и вовсю применяется подход, основная идея которого заключается в том, чтобы вместо самого изучаемого объекта использовать простые «кирпичики» с уже известными свойствами, которые склеиваются между собой и образуют его подобие, да-да, знакомый всем с детства конструктор. Зная свойства «кирпичиков», становится возможным подступиться и к свойствам самого объекта.

Гипотеза Ходжа в данном случае связана с некоторыми свойствами как «кирпичиков» так и объектов.

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

Всем нам еще со школы известны простые числа которые делятся только на себя и на единицу (2,3,5,7,11...) . С давних времен люди пытаются найти закономерность в их размещении, но удача до сих пор так никому и не улыбнулась. В результате ученые применили свои усилия к функции распределения простых чисел, которая показывает количество простых чисел меньше или равных определенного числа. Например для 4 - 2 простых числа, для 10 - уже 4 числа. Гипотеза Римана как раз устанавливает свойства данной функции распределения.

Многие утверждения о вычислительной сложности некоторых целочисленных алгоритмов, доказаны в предположении верности этой гипотезы.

Теория Янга - Миллса

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

На основе теории Янга-Миллса построена стандартная модель физики элементарных частиц в рамках которой был предсказан и не так давно обнаружен нашумевший бозон Хиггса.

Существование и гладкость решений уравнений Навье - Стокса

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

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

Для уравнения x 2 + y 2 = z 2 в свое время еще Эвклид дал полное описание решений, но для более сложных уравнений поиск решений становится чрезвычайно трудным, достаточно вспомнить историю доказательства знаменитой теоремы Ферма, чтобы убедиться в этом.

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

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

Гипотеза Пуанкаре

Думаю если не все, то большинство точно о ней слышали. Чаще всего встречается, в том числе и на центральных СМИ, такая расшифровка как «резиновую ленту натянутую на сферу можно плавно стянуть в точку, а натянутую на бублик - нельзя ». На самом деле эта формулировка справедлива для гипотезы Тёрстона, которая обобщает гипотезу Пуанкаре, и которую в действительности и доказал Перельман.

Частный случай гипотезы Пуанкаре говорит нам о том, что любое трехмерное многообразие без края (вселенная, например) подобно трехмерной сфере. А общий случай переводит это утверждение на объекты любой мерности. Стоит заметить, что бублик, точно так же как вселенная подобна сфере, подобен обычной кофейной кружке.

Заключение

В настоящее время математика ассоциируется с учеными, имеющими странный вид и говорящие о не менее странных вещах. Многие говорят о ее оторванности от реального мира. Многие люди как младшего, так и вполне сознательного возраста говорят, что математика ненужная наука, что после школы/института, она нигде не пригодилась в жизни.

Но на самом деле это не так - математика создавалась как механизм с помощью которого можно описать наш мир, и в частности многие наблюдаемые вещи. Она повсюду, в каждом доме. Как сказал В.О. Ключевский: «Не цветы виноваты, что слепой их не видит».

Наш мир далеко не так прост, как кажется, и математика в соответствии с этим тоже усложняется, совершенствуется, предоставляя все более твердую почву для более глубокого понимания существующей реальности.

Знаменитый британский математик Майкл Атья, профессор Оксфордского, Кембриджского и Эдинбургского институтов и лауреат почти десятка престижных премий в области математики, представил доказательство гипотезы , одной из «задач тысячелетия». Доказательство занимает всего 15 строк, а вместе с введением и списком литературы — пять страниц. Текст Атья выложил на сервисе Drive.

Гипотеза о распределении нулей дзета-функции Римана была сформулирована математиком Бернхардом Риманом в 1859 году.

Она описывает, как расположены на числовой прямой простые числа.

В то время как не найдено какой-либо закономерности, описывающей распределение простых чисел среди натуральных, Риман обнаружил, что количество простых чисел, не превосходящих x, — функция распределения простых чисел, обозначаемая π(x) — выражается через распределение так называемых «нетривиальных нулей» дзета-функции.

Гипотеза Римана утверждает, что все нетривиальные нули дзета-функции лежат на вертикальной линии Re=0,5 комплексной плоскости. Гипотеза Римана важна не только для чистой математики — дзета-функция постоянно всплывает в практических задачах, связанных с простыми числами, например, в криптографии.

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

Гипотеза Римана входит в список семи «задач тысячелетия», за решение каждой из которых Математический институт Клэя в США обязывается выплатить награду в один миллион долларов США.

Если доказательство будет подтверждено, Атья получит награду.

Математический институт Клэя объявил о своем решении отдать премию Перельману 19 марта 2010 года. Работы, за которые математик удостоился награды, были написаны им в 2002 году, причем они были выложены в архив электронных препринтов, а не напечатаны в рецензируемом научном журнале. В своих выкладках Перельман завершил доказательство гипотезы геометризации Терстона, которая прямо связана с гипотезой Пуанкаре.

В 2005 году за эти работы Перельману была присуждена Филдсовская премия, которую часто называют Нобелевской премией для математиков. От этой награды российский математик также отказался.

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

Для того чтобы признать решение Отелбаева верным, научное сообщество должно его проверить. Пока что результаты проверки неизвестны.

В 2010 году американский математик индийского происхождения Винай Деолаликар , что решил еще одну из задач тысячелетия — нашел доказательство неравенства классов сложности P и NP.

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

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