Миллион долларов за решение уравнения

Миллион долларов за решение уравнения

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

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

Все мы помним ещё со школы ряд таких чисел, которые можно поделить только на само себя и на один. Они называются простыми (1, 2, 3, 5, 7, 11, 13, 17. ). Самое большое из известных на сегодня простых чисел было найдено в августе 2008 года и состоит из 12 978 189 цифр. Для математиков эти числа очень важны, но как они распределяются по числовому ряду до сих пор до конца не ясно.

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

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

Уравнения Навье-Стокса

Уравнения Навье-Стокса являются основой для расчетов в геофизической гидродинамике, в том числе для описания движения течений в мантии Земли. Используются эти уравнения и в аэродинамике.

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

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

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

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

В 1941 году профессор Кембриджа Вильям Ходж предположил, что любое геометрическое тело можно исследовать как алгебраическое уравнение и составить его математическую модель.

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

Достижение Ходжа в том, что он описал такие условия, при которых не будут возникать «лишние» части, и не будут теряться необходимые. И все это при помощи алгебраических вычислений. Ни доказать его предположение, ни опровергнуть математики не могут уже 70 лет. Если это получится у вас — станете миллионером.

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

Уравнения вида xn + yn + zn + … = tn были известны ещё математикам древности. Решение самого простого из них («египетский треугольник» — 32 + 42 = 52) было известно ещё в Вавилоне. Его полностью исследовал в III веке нашей эры александрийский математик Диофант, на полях «Арифметики» которого Пьер Ферма сформулировал свою знаменитую теорему.

В докомпьютерную эпоху самое больше решение этого уравнения было предложено в 1769 году Леонардом Эйлером (2 682 4404 + 15 365 6394 + 18 796 7604 = 20 615 6734).

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

В 1960 году математикам Берчу и Свинертон-Дайеру, экспериментировавшим на компьютере с некоторыми известными кривыми, удалось создать метод, сводящий каждое такое уравнение к более простому, называемому дзета-функцией. По их предположению, если эта функция в точке 1 будет равна 0, то количество решений искомого уравнения будет бесконечным. Математики предположили, что это свойство будет сохраняться для любых кривых, но ни доказать, ни опровергнуть это предположение пока никто не смог.

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

Проблема Кука-Левина

Проблема решения-проверки Кука-Левина заключается в том, что на проверку любого решения уходит меньше времени, чем на решение самой задачи. Если наглядно: мы знаем, что где-то на дне океана есть клад, но не знаем, где именно. Его поиски могут проходить поэтому бесконечно долго. Если же мы знаем, что клад находится в таком-то квадрате, определенном заданными координатами, то поиск клада существенно упростится.

И так всегда. Скорее всего. Пока что никому из математиков и простых смертных не удалось найти такую задачу, решение которой заняло бы меньше времени, чем проверка правильности её решения. Если вдруг у вас получится найти такую — срочно пишите в институт Клэя. Если комиссия математиков одобрит — миллион долларов у вас в кармане.

Проблема Кука-Левина была сформулирована ещё в 1971 году, но до сих пор никем не решена. Её решение может стать настоящей революцией в криптографии и системах шифрования, поскольку появятся «идеальные шифры», взлом которых будет фактически невозможен.

Задача на миллион: P=NP?

За решение этой задачи из области алгоритмов готовы дать миллион долларов. И, если равенство докажут, это приведёт к величайшей революции в компьютерных науках.

Представьте, что вы заходите в кафе и ищете вашего друга. Если вам скажут, что он сидит за крайним столиком слева, вы тут же сможете проверить, так ли это. Означает ли это, что можно построить алгоритм, с помощью которого вы смогли бы также быстро отыскать вашего друга без подобной подсказки? Другими словами, можно ли решить задачу столь же быстро, как и проверить какое-то её решение? На удивление ответ вовсе не так очевиден, как вам кажется.

Таким незамысловатым способом можно представить себе суть одной из математических задач тысячелетия — задаче равенства классов P и NP. Даже если вы далеки от математики и информатики, я постараюсь рассказать вам об этой задаче так, чтобы вы оценили её изящную сложность.

Задачи тысячелетия

Чтобы грамотно подступиться к задаче равенства классов P и NP, сперва необходимо сделать небольшое отступление касательно института Клэя и списка из 7 задач тысячелетия.

Математический институт Клэя — это частная некоммерческая организация, которая занимается спонсированием многообещающих математиков и в целом распространением математических знаний. Этот институт известен благодаря публикации списка из 7 задач тысячелетия, каждая из которых представляет собой классическую математическую задачу, которая не решена на протяжении очень долгого времени. Помимо этого, за верное решение любой из 7 проблем объявлено вознаграждение в виде 1 000 000 долларов США. На сегодняшний момент из всего списка решена лишь 1 задача — гипотеза Пуанкаре, решение которой принадлежит российскому математику Григорию Перельману.

Как нетрудно догадаться, равенство классов P и NP является одной из 7 задач в данном списке, что подчеркивает её колоссальную сложность и фундаментальность.

Начнём с алгоритмов

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

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

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

Сейчас мне придётся прибегнуть к некоторым упрощениям, чтобы объяснить различные зависимости. Например, время работы программы описывается линейной функцией. Это будет означать, что если вы увеличите объём входных данных в 3 раза, время работы программы также возрастет в 3 раза. Если же, к примеру, зависимость времени работы от размера входных данных описывается квадратичной функцией, то при увеличении объёма входных данных в 3 раза время работы алгоритма возрастает в 9 раз.

Если зависимость времени работы программы от объёма входных данных описывается линейной, квадратичной, кубической и другими функциями, мы говорим о полиномиальном времени работы. Причина довольно-таки простая: линейная, квадратичная, кубическая и так далее функции являются полиномами, то есть многочленами от некоторого числа переменных. Понятие полиномиального времени работы довольно скоро нам пригодится.

Стоит отметить, что время работы программы может иметь не только полиномиальную зависимость от объема входных данных. Характер роста может быть куда более взрывным. Классический пример: экспоненциальная зависимость, при которой увеличение входных данных всего на 1 единицу измерения повлечёт увеличение времени работы алгоритма в некоторое константное количество раз.

Опять же упрощая, можно сказать, что полиномиальные алгоритмы — это быстрые алгоритмы, а те же экспоненциальные — нет.

Переходим к классам задач P, NP и NP-complete

Класс задач P определяется довольно просто — это набор таких задач, для которых мы знаем алгоритм, работающий за полиномиальное время. Для простоты можно считать, что класс P — это класс простых задач, поскольку мы знаем быстрые алгоритмы для их решения. Примеры задач из класса P: сложение двух чисел, сортировка множества из n элементов, поиск элемента в некотором множестве, выяснение связности графа и так далее.

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

Ещё более сложные задачи — это задачи из класса NP-complete. Если вам удаётся свести решение задачи А к решению задачи Б, то последняя задача как минимум настолько же сложная, как и первая. Суть NP-complete класса в том, что к любой задаче из данного класса можно свести абсолютно все задачи из класса NP, то есть каждая задача из данного класса настолько же сложна, как и любая задача из NP. Примеры задач из класса NP-complete: задача о ранце или та же задача коммивояжёра.

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

Теперь, когда мы разобрались в понятиях, мы можем сформулировать интересующую нас задачу. Правда, формулировка явно следует из названия: равны ли P и NP? Возможно ли построить для всех задач из NP полиномиальный алгоритм? Другими словами, если мы имеем задачу из класса NP и мы знаем, что для неё можно быстро проверить решение, означает ли это, что данное решение можно столько же быстро найти?

Зачем мы вводили класс NP-complete?

Это связано с одним очень интересным моментом касательно доказательства «P против NP». В классе P содержится огромное количество задач, равно как и в классе NP. Помимо этого, умнейшие учёные компьютерных наук на протяжении десятилетий пытались построить быстрый (полиномиальный) алгоритм хотя бы для одной из многих сотен задач из класса NP. Тем не менее, учитывая, что любая NP-complete задача настолько же сложная, как и все задачи из NP, если хотя бы для одной NP-complete задачи нам удастся доказать, что её можно быстро решить, мы автоматически докажем то же самое для всех задач из класса NP.

Почему это важно?

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

Значительно более эффективное решение подобных проблем могло бы сэкономить серьёзные деньги, а также время, поскольку с современными алгоритмами мы не можем решить достаточно быстро, и нам приходится довольствоваться лишь приближенными решениями.

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

Почему это особенно важно для криптографии?

Стоит понимать, что солидная часть криптографии (например, криптографические системы с открытым ключом) строится на предположении, что некоторые вещи нельзя выполнить быстро (чуть более точно: нельзя построить быстрый алгоритм для некоторых задач). Например, быстро разложить число на простые множители. Если выяснится, что P = NP, и мы способны построить быстрые алгоритмы для задач из класса NP (вроде разложения числа на простые множители), то многие методы защиты сразу же устареют, поскольку у каждого желающего будет быстрый алгоритм, способный обойти защиту.

Так P равно NP или нет?

Большинство современных специалистов сходится во мнении, что P не равно NP. Некоторое интуитивное объяснение этому мы уже давали: на протяжении десятилетий лучшие умы компьютерных наук пытались построить быстрые алгоритмы для задач из классов NP и NP-complete, но это ни разу не увенчалось успехом. Кроме того, в 2002 и 2012 годах было проведено голосование «равны ли P и NP» с четырьмя вариантами ответов: нет, да, не уверен, вопрос независим с современной системой аксиом и поэтому теорему невозможно доказать или опровергнуть. Результаты были следующими (в процентах): 61/83, 9/9, 22/5, 8/3. Другими словами, в рамках последнего голосования 83 процента опрошенных верят, что P не равно NP.

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

Решена одна из «задач тысячелетия»

Американский математик Мартин Дауд опубликовал решение одной из «задач тысячелетия» — доказательство неравенства классов сложности P и NP. За решение каждой из этих задач Математический институт Клэя назначил премию в миллион долларов США. В настоящее время научное сообщество изучает его результаты.

«Задачи тысячелетия» — это семь математических проблем, считающихся важными классическими задачами, которые оставались нерешенными в течение многих лет. За решение каждой из них Институт имени Клэя назначил вознаграждение в 1 млн долларов. До сих из «задач тысячелетия» была решена только одна — российский математик Григорий Перельман доказал гипотезу Пуанкаре, однако отказался от премии.

Теперь американский математик Мартин Дауд, сотрудник Hyperon Software, опубликовал решение еще одной «задачи тысячелетия». Он представил пятистраничное доказательство неравенства классов сложности P и NP. В настоящее время научное сообщество изучает его результаты, и об их достоверности судить пока рано.

Вопрос о равенстве классов сложности P и NP представляет одну из центральных проблем современной информатики. Задача заключается в следующем: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти? То есть, действительно ли задачу в этом случае легче проверить, чем решить? В теории алгоритмов множество вычислительных задач, примерно одинаковых по сложности вычисления, называется классом сложности. Класс P — это вычислительные задачи, которые легко решить, а NP — задачи, для которых легко проверить, верно ли предполагаемое решение.