Cайт веб-разработчика, программиста Ruby on Rails ESV Corp. Екатеринбург, Москва, Санкт-Петербург, Первоуральск

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

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

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

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

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

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

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

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

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

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

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

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

Ученые уже во всю применяют данную методику, но доказать ее справедливость, что любой, не важно на сколько сложный объект, можно сложить из более простых, пока не удается.

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

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

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

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

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

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

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

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

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

Данная гипотеза связана с описанием некоторых алгебраических уравнений — так называемых эллиптических кривых. Примером подобного уравнения является выражение x2 + y2 = z2. Эвклид дал полное описание решений этого уравнения, но для более сложных уравнений поиск решений становится чрезвычайно трудным. Данная гипотеза является единственным относительно простым общим способом вычисления ранга, одного из важнейших свойств эллиптических кривых.

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

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

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

Заключение

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

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

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

habrahabr.ru