Семь проблем тысячелетия. От проблемы Кука до проблемы Путника! Что значит материальный стимул

Лист Мёбиуса иногда ошибочно называют лентой. Это неправильно потому, что лента должна быть ограничена двумя кривыми, или краями. Как нетрудно убедиться, у листа Мёбиуса не только одна сторона, у него и всего одна кромка. По этой кромке его можно вклеить в сферу, если в ней прорезать отверстие. Поверхность, которая получится в итоге, называют проективной плоскостью. Она не только двухмерная, как и поверхность сферы или тора, но и односторонняя, как поверхность листа Мёбиуса. Вдобавок к этому ее нельзя вложить в обычное трехмерное пространство, а потому и представить ее себе выше человеческих сил. Фото (Creative Commons license): Dave Gough

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

Почем проблема

По сравнению с прошлым столетием количество таких проблем сократилось почти в четыре раза. Когда в самом начале XX века знаменитый немецкий математик Давид Гильберт (David Hilbert , 1862-1943) выступил на международном математическом конгрессе в Париже , представленный им список математических и логических задач, которые предстояло решить в ближайшие сто лет, насчитывал 23 позиции. Плюс еще три проблемы, с которых он начал свою речь и которые, будучи уже упомянутыми, не вошли в основной список. Настолько они казались Гильберту само собой разумеющимися. А одна из самых красивых — задача о равносоставленности многогранников одинакового объема — была решена за несколько лет до того, как Гильберт ее поставил.

Первой из упомянутых им и последней из решенных проблем (всего к концу века двадцать из них было решено полностью) стало доказательство знаменитой Великой теоремы Ферма (Fermat’s Last Theorem). Две из оставшихся проблем были решены частично, две открыты до сих пор, одна, о математическом описании физических аксиом, признана нематематической, и одна, о прямой как кратчайшем соединении двух точек, была объявлена слишком расплывчатой, из-за чего невозможно было понять, решена она или нет.

Новый список проблем, составленный уже в начале этого века, насчитывает всего семь задач. Коренное отличие нынешнего списка, названного «Задачи тысячелетия» (Millennium Prize Problems), состоит в том, что за решение каждой из них частный некоммерческий фонд, основанный в 1998 году в американском Кембридже бостонским бизнесменом Лэндоном Клеем (Landon T. Clay), назначил премию в 1 млн. Вернее сказать, наоборот: проблем было выбрано именно семь по числу выделенных на их решение миллионов. Решение проблем Гильберта никакого вознаграждения, кроме вечной научной славы и глубокого научного же удовлетворения, не подразумевало.

Что значит материальный стимул

Первый миллион Клея был присужден 18 марта 43-летнему российскому математику, в недавнем прошлом сотруднику Григорию Яковлевичу Перельману, доказавшему справедливость так называемой гипотезы Пуанкаре (Poincaré Conjecture).

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

Судьба оставшихся миллионов

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

Уравнения вида x n + y n + z n + … = t n на множестве целых чисел привлекали внимание математиков с античных времен. Решения самого простого из них x 2 + y 2 = z 2 (например, знаменитых «египетский треугольник» — 3 2 + 4 2 = 5 2) было известно еще в Вавилоне, а полностью его исследовал еще в III веке н. э. александрийский математик Диофант (Διόφαντος ὁ Ἀλεξανδρεύς, Diophantus, III век н.э.). Именно на полях его «Арифметики» написал формулировку своей знаменитой теоремы Пьер Ферма (Pierre de Fermat , 1601 или 1607/8-1665). А одно из самых больших решений (в докомпьютерную эпоху) предложил в 1769 году Леонард Эйлер (1707-1783). Ему удалось соорудить следующее равенство: 2 682 440 4 + 15 365 639 4 + 18 796 760 4 = 20 615 673 4 .

Универсального метода вычисления для подобных уравнений не существует. Однако еще во времена долгих безуспешных попыток доказать теорему Ферма стало известно об их связи с простыми числами, а потом и с некоторыми классами плоских кривых. Корни диофантовых уравнений, простые числа и точки пересечения плоских кривых описываются с помощью некоторых специальных функций — например, дзета-функции Римана или ее обобщения, L -функции Гассе-Вейля . Математики Берч (Bryan John Birch) и Свинертон-Дайер (Sir Henry Peter Francis Swinnerton-Dyer) в 1960 году, экспериментируя на компьютере с некоторыми известными кривыми, обнаружили для них довольно простое поведение L -функции вблизи нулей. Тогда они предположили, что это свойство будет сохраняться для любых кривых. Ни доказать, ни опровергнуть это предположение пока никто не смог. Если считаете, что доказать это вам не под силу, найдите пример, при котором свойство не сработает, и можете считать, что миллион у вас в кармане. Ведь для его получения вполне достаточно и опровергнуть гипотезу даже простым частным случаем.

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

Исследовать сложный объект тем сложнее, чем сложнее он устроен. Поэтому математики обычно сначала пытаются разложить его на объекты более простые, работать с которыми, как понятно, проще. Проблема в том, что просто разложить объект на составляющие получается далеко не всегда. Иногда при этом возникают новые части, неизвестно откуда взявшиеся и непонятно что из себя представляющие. Либо, наоборот, при более детальном исследовании выясняется, что каких-то деталей явно не хватает. Проще говоря, исследуя просто кирпичи, мы не можем себе представить, что собой представляет составленный из них дом, как он выглядит и по каким правилам его строят. Для этого нужно, как минимум, изучить еще и заключенное между ними пустое пространство комнат. Профессор Кембриджа Вильям Ходж (William Vallance Douglas Hodge , 1903-1975) в своих трудах в 1941 году описал условия, при которых, как ему кажется, такие непонятные «лишние» части не могут возникать и в которых любое геометрическое тело можно исследовать как алгебраическое уравнение, составив его математическую модель. Ни доказать его предположение, ни опровергнуть его ученые не могут уже почти 70 лет.

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

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

Проблема Решения-Проверки (Проблема Кука-Левина)

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

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

Среди всей массы чисел особое место занимают числа, которые невозможно разделить ни на что более мелкое, чем они сами: 1, 2, 3, 5, 7, 11, 13, 17 и так далее. Такие числа называются «простыми», и они для математиков крайне важны. Как они распределяются по числовому ряду — пока известно одному Богу. Риман в 1859 году даже не предложил способ их поиска или проверки. Проверить, является ли число простым или нет, можно только попробовав разделить его на все меньшие его простые числа (самое большое из известных на сегодняшний день простых было найдено в августе 2008 года и состоит из 12 978 189 цифр). Он просто нашел метод, по которому можно определить максимальное количество простых чисел, не превышающих некое заданное число. На сегодня математики проверили этот метод с полутора триллионами «простых». Сбоев пока найдено не было. Однако это вовсе не говорит о том, что метод не споткнется на полтора триллиона первой проверке. А поскольку гипотеза Римана, перешедшая в новый список еще из списка Гильберта, активно используется для расчета систем безопасности передачи данных в сотовых сетях, в сети Интернет и так далее, ее доказательство имеет весьма практический смысл. И миллион здесь платить есть за что.

Уравнения Янга-Миллса

Свои квантовые уравнения американские физики Чжэнь-нин Янг (Chen-Ning Franklin Yang) и Роберт Миллс (Robert L. Mills, 1927-1999) составили в 1954 году, исходя из самых общих представлений о симметрии элементарных частиц . Несмотря на формальность подхода, уравнения замечательно описывают почти все известные виды взаимодействий — сильное, слабое и электромагнитное. С помощью уравнений даже было предсказано открытие новых частиц, которые потом были действительно найдены в экспериментах, проведенных в крупнейших лабораториях мира — Brookhaven, Stanford и CERN. Но при этом до сих пор непонятно, как они работают и, вообще, так ли уж они верны. Из всех вышеперечисленных уравнений эти — наиболее сложные, поэтому мы их приводить не будем. Но если вам не хватит пяти миллионов, которые можно получить за решение предыдущих пяти проблем, никто вам не запретит постараться решить еще и эту. Дерзайте и обрящете.

Новости партнёров

Семь проблем тысячелетия

Template 1. Проблема Кука (сформулирована в 1971 г.)
Допустим, находясь в большой компании, вы хотите убедиться, что там же находится ваш знакомый. Если вам скажут, что он сидит в углу, то вам достаточно доли секунды, чтобы, бросив взгляд, убедиться в истинности информации. В отсутствие этой информации вы будете вынуждены обойти всю комнату, рассматривая гостей. Это говорит о том, что решение какой-либо задачи часто занимает больше времени, чем проверка правильности решения.
Стивен Кук сформулировал проблему: может ли проверка правильности решения задачи быть более длительной, чем само получение решения, независимо от алгоритма проверки. Эта проблема является одной из нерешенных проблем логики и информатики. Ее решение могло бы революционным образом изменить основы криптографии, используемой при передаче и хранении данных.

2. Гипотеза Римана (сформулирована в 1859 г.)
Некоторые целые числа не могут быть выражены как произведение двух меньших целых чисел, например 2, 3, 5, 7 и т. д. Такие числа называются простыми числами, и они играют важную роль в чистой математике и ее приложениях. Распределение простых чисел среди всех натуральных чисел не подчиняется никакой закономерности. Однако немецкий математик Риман сделал предположение, касающееся свойств последовательности простых чисел. Если гипотеза Римана будет доказана, то это приведет к революционному изменению наших знаний в области шифрования и к невиданному прорыву в области безопасности Интернета.

3. Гипотеза Берча и Свиннертон-Дайера (сформулирована в 1960 г.)
Связана с описанием множества решений некоторых алгебраических уравнений от нескольких переменных с целыми коэффициентами. Примером алгебраического уравнения является уравнение x2 + y2 = z2. Евклид дал полное описание решений этого уравнения, но для более сложных уравнений получение решения становится чрезвычайно трудным.

4. Гипотеза Ходжа (сформулирована в 1941 г.)
В ХХ веке математики открыли мощный метод исследования формы сложных объектов. Основная идея заключается в том, чтобы использовать вместо самого объекта простые "кирпичики", которые склеиваются между собой и образуют его подобие. Гипотеза Ходжа связана с некоторыми предположениями относительно свойств таких "кирпичиков" и объектов.

5. Уравнения Навье - Стокса (сформулированы в 1822 г.)
Если плыть в лодке по озеру, то возникнут волны, а если лететь в самолете, в воздухе возникнут турбулентные потоки. Предполагается, что эти и другие явления описываются уравнениями, известными как уравнения Навье - Стокса. Решения этих уравнений неизвестны, и при этом даже неизвестно, как их решать. Необходимо показать, что решение существует и является достаточно гладкой функцией. Решение этой проблемы позволит существенно изменить способы проведения гидро- и аэродинамических расчетов.

6. Проблема Пуанкаре (сформулирована в 1904 г.)
Если натянуть резиновую ленту на яблоко, то можно, медленно перемещая ленту без отрыва от поверхности, сжать ее до точки. С другой стороны, если ту же самую резиновую ленту соответствующим образом натянуть вокруг бублика, то никаким способом невозможно сжать ленту в точку, не разрывая ленту или не ломая бублик. Говорят, что поверхность яблока односвязна, а поверхность бублика - нет. Доказать, что односвязна только сфера, оказалось настолько трудно, что математики до сих пор ищут ответ.

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

Last Update: 05/10/2019 02:40 +0300

Честь быть "первой" NP-полной задачей выпала на долю задачи распознавания из булевской логики, задачи, которую обычно называют ВЫПОЛНИМОСТЬ (сокращенно ВЫП). Тер­мины, использующиеся для ее описания, определяются следую­щим образом.

Пусть U = (u 1 , u 2 , ..., u m } - множество булевских пере­менных. Под набором значений истинности на множестве U бу­дем понимать функцию t: U→{T, F}. Если t(u)= Т, то будем говорить, что u принимает значение "истина" относительно t; если t(u) = F, то будем говорить, что и принимает значение "ложь". Если u - переменная из U, то u и и назовем литера­лами из U. Литерал и принимает значение "истина" относитель­но t в том и только в том случае, если переменная и принимает значение "истина" относительно t; литерал и принимает значе­ние истина в том и только в том случае, если переменная “при­нимает значение "ложь".

Дизъюнкцией над U назовем множество литералов над U, на­пример {u 1 , u 3 , u 8 }. Она представляет дизъюнкцию этих лите­ралов и называется выполненной при некотором наборе значений истинности тогда и только тогда, когда при рассматриваемом наборе значений истинности хотя бы один из ее членов прини­мает значение "истина". В нашем примере дизъюнкция будет выполнена относительно t, если одновременно не окажется, что t(u 1) = F, t(u 3) = T, t(u 8) = F. Набор С дизъюнкций над U называется выполнимым в том и только в том случае, если найдется некоторый набор значений истинности на множестве U, такой, что одновременно выполнены все дизъюнкции из С. Такой набор значений истинности называется выполняющим на­бором значений истинности для С. Задача ВЫПОЛНИМОСТЬ формулируется следующим образом:

ВЫПОЛНИМОСТЬ

УСЛОВИЕ. Заданы множество переменных U и набор С дизъ­юнкций над U.

ВОПРОС. Существует ли выполняющий набор значений истин­ности для С?

Например, пусть U = {u 1 , u 2 } и С= {{u 1 , u 2 }, {u 1 , u 2 }}. Это индивидуальная задача из ВЫП, ответ на которую есть "да". Выполняющее задание значений истинности определяется так: t(u 1) = t(u 2) = Т. С другой стороны, заменив С на С" = {{u 1 , u 2 }, {u 1 , u 2 }, {u 1 }}, получим пример индивидуальной за­дачи, ответ на которую есть "нет", поскольку С" невыполнима. Теперь можно сформулировать фундаментальную теорему Кука .

Теорема 2.2 (теорема Кука). Задача ВЫПОЛНИМОСТЬ есть NP -полная задача.

Доказательство . Легко видеть, что ВЫП лежит в классе NP. Недетерминированному алгоритму для ее решения достаточно указать набор значений истинности на исходном множестве пе­ременных и осуществить проверку того, что этот набор значений выполняет все дизъюнкции из исходного набора С. Все это легко сделать (недетерминированным образом) за полиномиаль­ное время. Таким образом, первое требование, которому должны удовлетворять NP-полные задачи, выполнено.

Для того чтобы проверить выполнение второго требования, вернемся к уровню языков, т. е. к представлению ВЫП языком Lвып = L[ВЫП, е] для некоторой разумной схемы кодирова­ния е. Необходимо показать, что для всех языков L е NP имеет место соотношение L ∞ Lвып. Разные языки из NP могут сильно отличаться; число этих языков бесконечно, поэтому невозможно указать отдельное сведение для каждого из них. Однако каждый язык из NP может быть представлен в стандартном виде, а именно НДМТ-программой, работающей полиномиальное время и распознающей этот язык.

Такое представление позволяет иметь дело с общей НДМТ-программой, время работы которой полиномиально, и получить общую сводимость языка, распознаваемого этой программой, к Lвып- Если эту общую сводимость специализировать для кон­кретной НДМТ-программы М, распознающей Lм, то получится искомое полиномиальное сведение Lм к Lвып. Таким образом, по существу, для всех L ε NP будет представлено общее дока­зательство того, что L ∞ Lвып.

Вначале рассмотрим произвольную НДМТ-программу М с полиномиальным временем работы, которая имеет компоненты Г, Σ, b, Q, q 0 , q y , q n , δ и распознает язык L = L M . Кроме того, пусть р(n) - полином с целыми коэффициентами, ограничиваю­щий сверху временную сложность Т м (n). (Не умаляя общно­сти, можно считать, что р(n) ≥ n для всех n ε Z+.) Функция f L , реализующая общую сводимость, будет описана в терминах М, Г, Σ, b, Q, q 0 , q Y , q n , δ и р.

Удобно рассматривать f L как отображение из множества слов в алфавите 2 в индивидуальные задачи из ВЫП, а не в слова в алфавите S, которые кодируют задачи из ВЫП, так как детали, связанные с кодированием, могут быть легко вос­полнены. Таким образом, функция f l будет обладать тем свой­ством, что для всех x ε Σ* принадлежность x ε L имеет место в том и только в том случае, если для набора дизъюнкций f l (x) имеется выполняющий набор значений истинности. Ключом к построению функции f L является использование некоторого на­бора дизъюнкций для записи утверждения, что х принимается НДМТ-программой М, т. е. утверждение x ε L.

Если входное слово х ε Σ* принимается программой М, то для х существует принимающее вычисление программы М, та­кое, что число шагов на стадии проверки и число символов в слове-догадке ограничены величиной р(n), где n = |x|. В таком вычислении будут участвовать лишь ячейки с номерами от -р(n) до р(n)+1. Это следует из того, что читающая/пишу­щая головка начинает работу в ячейке с номером 1 и на каж­дом шаге сдвигается не более чем на 1 ячейку. Проверяющее вычисление полностью определяется заданием в каждый мо­мент времени содержания ячеек с указанными номерами, вну­треннего состояния и положения читающей/пишущей головки. Далее, поскольку в проверяющем вычислении имеется не более р(n) шагов, то необходимо учесть не более р(n)+1 моментов времени. Это позволяет полностью описать такое вычисление, используя полиномиально ограниченное число булевских пере­менных и некоторый набор значений истинности на их мно­жестве.

Множество переменных U, участвующих в описании функции f L , предназначено именно для указанных целей. Перенумеруем элементы множеств Q и Г следующим образом: Q: q 0 , q 1 = q y , q 2 = q N , q s , ..., q r , где r = |Q|; Г: s 0 = b, s 1 s 2 , ..., s v , где v=|Г| - 1. В дальнейших рассуждениях будут участвовать три типа переменных, каждому из которых придается опреде­ленный смысл согласно рис. 2.7. При этом фраза "в момент времени i" служит сокращением точного выражения "после вы­полнения j-ro шага проверяющего вычисления".

Вычисление программы М очевидным образом индуцирует на множестве этих переменных набор значений истинности, если принять соглашение, что при окончании вычисления раньше мо­мента времени р(n) конфигурация остается неизменной во все моменты времени после остановки, т. е. сохраняются заключи­тельное состояние, положение головки и запись на ленте. В ну­левой момент времени запись на ленте состоит из входного слова х, расположенного в ячейках с номерами от 1 до n, и слова-догадки w в ячейках с номерами от -1 до |w|, при этом все остальные ячейки пусты.

С другой стороны, произвольный набор значений истинности этих переменных не обязательно соответствует какому-то вы­числению, а тем более принимающему. При произвольном на­боре значений истинности переменных в некоторой ячейке могли

рис. 2.7. Переменные набора дизъюнкции fl (x ) и придаваемый им смысл

бы быть одновременно записаны несколько различных симво­лов, машина могла бы находиться одновременно в нескольких различных состояниях, а читающая/пишущая головка могла бы одновременно просматривать любое подмножество ячеек с но­мерами от -р(n) до р(n)+1. Описание функции f L осущест­вляется посредством построения такого набора дизъюнкций, со­держащего перечисленные переменные, что набор значений истинности будет выполняющим тогда и только тогда, когда этот набор значений истинности индуцируется некоторым при­нимающим вычислением на входе х, причем стадия проверки этого вычисления выполняется не более чем за р(n) шагов и слово-догадка имеет длину не более р(n). Таким образом мы получим импликации:

x ε L ↔ на входе х существует принимающее вычисление про­граммы М

↔ на входе х существует принимающее вычисление программы М, число шагов которого не превосходит р(n), а слово-догадка w имеет длину, равную р(n).

↔ существует выполняющее задание значений истинности для набора дизъюнкций задачи f l (x).

Это будет означать, что для f l выполнено одно из двух усло­вий, требующихся в определении полиномиальной сводимости. Другое условие, заключающееся в том, что fl должна быть вычислима за полиномиальное время, можно будет легко про­верить после того, как описание f l . будет закончено.

Дизъюнкции индивидуальной задачи f i (x) можно подразде­лить на 6 групп, каждая из которых будет налагать ограничение определенного типа на любой выполняющий набор значений истинности. Эти группы показаны на рис. 2.8.

Рис. 2.8. Группы дизъюнкций для f L (х) и ограничения, накладываемые ими на выполняющий набор истинностных значений.

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

Группа G 1 состоит из следующих дизъюнкций:

{Q, Q, .... Q(i, r]}, 0

Первые р(n)+1 из этих дизъюнкций могут быть выполнены одновременно в том и только в том случае, если в каждый мо­мент времени i программа М находится по крайней мере в од­ном состоянии. Остальные (р(n)+1) (r + 1) (r/2) дизъюнкций могут быть выполнены одновременно в том и только в том слу­чае, если ни в один момент времени i программа М не находится более чем в одном состоянии. Таким образом, G1 выпол­няет свое назначение.

Группы G 2 и G 3 строятся аналогично, а группы G 4 и G 5 очень просты, каждая из них включает дизъюнкции, состоящие только из одного литерала. На рис. 2.9 дано полное описание первых пяти групп дизъюнкций. Отметим, что как число дизъюнкций в этих группах, так и максимальное число литералов, входящих в каждую дизъюнкцию, ограничены некоторым полиномом от n (так как r и v -константы, которые определяются по М и, зна­чит, по языку L).

Рис. 2.9. Первые 5 групп дизъюнкций для f L (х).

Несколько сложнее выглядит описание последней группы дизъюнкций - G 6 , которая гарантирует, что каждая следующая конфигурация машины получается из предыдущей в результате применения одной команды программы М. Эта группа состоит из двух подгрупп дизъюнкций.

Первая подгруппа гарантирует, что если читающая/пишущая головка в момент времени i не просматривает ячейку с номером j то символ в ячейке с номером j от момента времени i к мо­менту времени i + 1 не изменится. Дизъюнкции этой подгруппы имеют вид

Зафиксируем произвольно момент времени t, ячейку с номером j и символ s l Если в момент времени i читающая/пишущая головка не просматривает ячейку с номером j и в этой ячейке в момент времени i записан символ j, а в момент времени i + 1 его там уже нет, то указанная выше дизъюнкция не будет вы­полнена (в противном случае она будет выполнена). Таким об­разом, 2(р(n)+ l) 2 (v + 1) дизъюнкций этой группы выполняют свое назначение.

Вторая подгруппа дизъюнкций из группы G 6 гарантирует, что перестройка одной машинной конфигурации в следующую про­исходит согласно функции перехода δ программы М. Для каж­дой четверки

(i, j, k, l), 0 ≤ i < p(n), -р(n) ≤ j ≤ р(n) + 1, 0 ≤ k ≤ r и 0 ≤ l ≤ v,

эта подгpуппа содержит следующие три дизъюнкции:

где значения ∆, k" и l" определены так:

если q k ε Q\{q y , q N }, то δ(q k , s l) = (q k ` , s l ` , ∆),

а если q k ε {q Y , q N }, то ∆= 0, k" = k и l" = l.

Нетрудно понять (хотя для этого может потребоваться не­сколько минут раздумий), что эти 6(р(n))(р(n) + 1)(r+1)(v+1) дизъюнкций дают необходимое ограничение на выполняющий набор значений истинности.

Таким образом, мы показали, как построить группы дизъ­юнкций G 1 -G 6 , которые выполняют свое назначение. Если х ε L, то у программы М на входе х есть принимающее вычис­ление длины не более р(n), и это вычисление дает при заданной интерпретации переменных набор значений истинности, который выполнит все дизъюнкции из C=G 1 UG 2 UG 3 UG 4 UG 5 UG 6 . На­оборот, набор дизъюнкций С построен так, что любой выпол­няющий набор значений истинности для С обязан соответство­вать некоторому принимающему вычислению программы М на входе х. Отсюда следует, что для f l (x) имеется выполняющий набор значений истинности тогда и только тогда, когда х ε L.

Теперь осталось показать, что для любого фиксированного языка L индивидуальная задача f l (x) может быть построена за время, ограниченное полиномом от n = |x|. Если язык L задан, то можно выбрать некоторую НДМТ-программу М, которая распознает L за время, ограниченное полиномом р (нет необходи­мости за полиномиальное время находить саму недетерминиро­ванную программу, так как необходимо лишь показать, что ото­бражение f l существует). Если имеются определенная НДМТ-программа М и многочлен р, то построение множества перемен­ных U и набора дизъюнкций С требует чуть больше работы, чем заполнение всех позиций в стандартной (хотя и довольно слож­ной) формуле. Полиномиальная ограниченность этого вычисле­ния будет ясна, если мы покажем, что Length ограничена сверху полиномом от n, где Length [I], как указано в разд. 2.1, характеризует длину слова, кодирующего индивидуальную за­дачу I, при некоторой разумной схеме кодирования.

В качестве “разумной” функции длины для задачи ВЫП можно, например, взять |U||С|. Ни одна из дизъюнкций не может содержать более 2|U| литералов (т. к. общее число литералов равно 2|U|), а число символов, необходимое для описания каждого индивидуального литерала, не более log|U|, но этой величиной можно пренебречь, так как она дает полино­миальный вклад в общую длину задачи. Поскольку r и v фикси­рованы заранее, то они могут увеличить |U| и |С| в постоян­ное число раз, поэтому имеем |U| = O(р(n) 2) и |С| = O(р(n)) 2 . Следовательно, Length = |U|| С| = O(р(n) 4) и, значит, ограничена полиномом от n, что и требовалось.

Таким образом, преобразование f l может быть вычислено алгоритмом, имеющим полиномиальную временную сложность (однако конкретная полиномиальная граница для сложности будет зависеть от L, а также от выбора М и р), из чего можно заключить, что для всех L ε NP функция f L вычислима за поли­номиальное время и отображает L в ВЫП (точнее, отображает L в Lвып). Отсюда вытекает утверждение теоремы, что ВЫП есть NP-полная задача.▀

Доказательство результатов об NP -полноте

3-ВЫПОЛНИМОСТЬ (3-ВЫП)

УСЛОВИЕ. Дан набор С= {с 1 , с 2 , ..., с m } дизъюнкций на ко­нечном множестве переменных U, таких, что |с i | = 3, 1 ≤ i ≤ m.

ВОПРОС. Существует ли на U набор значений истинности, при котором выполняются все дизъюнкции из С?

ТРЕХМЕРНОЕ СОЧЕТАНИЕ (3-С)

УСЛОВИЕ. Дано множество M ε W x X x Y, где W, X и У - непересекающиеся множества, содержащие одинаковое число элементов q.

ВОПРОС. Верно ли, что М содержит трехмерное сочетание, т. е. подмножество М" ε M, такое, что |М`|=q и никакие два разных элемента М" не имеют ни одной равной координаты?

ВЕРШИННОЕ ПОКРЫТИЕ (ВП)

УСЛОВИЕ. Дан граф G =(V, E) и положительное целое число K, K ≤ |V|.

ВОПРОС. Имеется ли в графе G вершинное покрытие не более нем из К элементов, т. е. такое подмножество V" ε V, что |V`| ≤ K и для каждого ребра {u, v} ε Е хотя бы одна из вершин u или v принадлежит V`?

КЛИКА

УСЛОВИЕ. Дан граф G=(V, E) и положительное целое число J ≤ |V|.

ВОПРОС. Верно ли, что G содержит некоторую клику мощно­сти не менее J, т. е. такое подмножество V` ε V, что |V`| ≥ J и любые две вершины из V соединены ребром из E?

ГАМИЛЬТОНОВ ЦИКЛ (ГЦ)

УСЛОВИЕ. Дан граф G=(V, E).

ВОПРОС. Верно ли, что G содержит гамильтонов цикл, т. е. такую последовательность вершин графа G, что n=|V|, (v n ,V 1) ε E и (v i , v i +1 }ε E для всех i, 1≤ i ≤ n.

РАЗБИЕНИЕ

УСЛОВИЕ. Заданы конечное множество А и "вес" s(a) ε Z+ для каждого а ε A.

ВОПРОС. Существует ли подмножество А" ε А, такое, что

3-выполнимость

Задача 3-ВЫПОЛНИМОСТЬ есть просто ограниченный вариант задачи ВЫПОЛНИМОСТЬ, в котором каждая индивидуальная задача имеет ровно три литерала в каждой дизъюнкции.) Из-за своей простой структуры эта задача наиболее часто применяется для доказательства результатов об NP-полноте.

Теорема 3.1. Задача 3-ВЫПОЛНИМОСТЬ является NP - полной.

Доказательство. Нетрудно видеть, что 3-ВЫП ε NP. Это следует из того, что недетерминированному алгоритму необходимо угадать лишь набор значений истинности переменных задачи и проверить за полиномиальное время, будут ли при таком [наборе значений истинности выполняться все заданные трехлитеральные дизъюнкции.

Сведем задачу ВЫП к задаче 3-ВЫП. Пусть U = {u 1 , u 2 , …, u n } - множество переменных и С= {с 1 , с 2 , ..., с m } - произвольный набор дизъюнкций, определяющий произвольную индивидуальную задачу из ВЫП. Построим набор С" трехлитеральных дизъюнкций на некотором множестве переменных U", такой, что С" выполним тогда и только тогда, когда выпол­ним С.

Набор С" будет строиться путем замены каждой отдельной дизъюнкции c j ε С "эквивалентным" набором С` j трехлитеральных дизъюнкций на множестве U исходных переменных и мно­жестве U" j некоторых дополнительных переменных, причем пе­ременные из U" j будут использоваться только в дизъюнкциях из С` j . Другими словами,

Таким образом, нужно только показать, как исходя из сj можно построить С` j и U` j . Пусть c j задается множеством {z 1 , z 2 , ..., z k }, где z i , - литералы на множестве U. Способ образования С` j и U" j зависит от значения k.

Для доказательства того, что здесь в самом деле имеет ме­сто сводимость, необходимо показать, что набор дизъюнкций С" выполним тогда и только тогда, когда выполним набор дизъюнкций С. Предположим вначале, что t: → {Т, F} есть набор значений истинности, выполняющий С. Покажем, что t может быть продолжен до набора значений истинности t": U" → {Т,Р}, который выполняет С". Поскольку переменные в мно­жестве U" \ U делятся на группы U` j и так как переменные в каждой группе U` j входят только в дизъюнкции, принадлежащие С` j , то достаточно показать, как t может быть продолжен на каждое множество U` j отдельно, и в каждом случае нужно про­верить, что выполняются все дизъюнкции в соответствующем множестве С` j .

Это можно сделать следующим образом. Если U` j построены, как в случае 1 или 2, то дизъюнкции из С` j уже выполнены с помощью t, поэтому t может быть продолжен на U` j произ­вольно, например, если положить t"(y) = T для всех y ε U" j . Если U" j построено, как в случае 3, то U` j - пусто и единствен­ная дизъюнкция в С` j уже выполнена с помощью t. Остается только случай 4, который соответствует дизъюнкции {z 1 , z 2 , ... ..., z k } из С, причем k > 3. Поскольку t - выполняющий набор значений истинности для С, то найдется такое целое l, что z l при t принимает значение истина. Если l = 1 или 2, то пола­гаем t"(y i j)=F, 1 ≤ i ≤ k - 3. Если l = k - 1 или k, то пола­гаем t"(y i j) = F, 1 ≤ .i ≤ k - 3. В противном случае полагаем t"(y ij) = T при 1 ≤ i ≤ l -2 и t" (yij) = F при l-1 ≤ i ≤ k -3. Легко проверить, что такой набор значений истинности обе­спечит выполнение всех дизъюнкций в С`j, поэтому t` выпол­няет все дизъюнкции из С". Обратно, если t" - некоторый выполняющий набор значений истинности для С", то легко проверить, что ограничение t" на переменные из U должно быть выполняющим набором значений истинности для С. Таким образом, С" выполним тогда и только тогда, когда выполним С.

Для того чтобы убедиться, что эта сводимость полиномиаль­ная, достаточно заметить, что число трехлитеральных дизъюнк­ций в С" ограничено полиномом от т.п. Следовательно, размер индивидуальной задачи 3-ВЫП ограничен сверху некоторым по­линомом от размера соответствующей задачи ВЫП, а так как все детали построения сводимости очевидны, то читателю будет нетрудно проверить, что эта сводимость является полиномиаль­ной.▀

Ограниченная структура задачи 3-ВЫП делает ее гораздо более полезной при доказательстве результатов об NP-полноте по сравнению с задачей ВЫП. Любое доказательство, основан­ное на задаче ВЫП (кроме только что приведенного), может быть легко перестроено в доказательство, основанное на 3-ВЫП, даже без изменения функции, осуществляющей сводимость. На самом деле дополнительное условие о том, что все дизъюнкции имеют одинаковую длину, часто может упростить сводимость, которую нужно построить, и тем самым облегчить ее отыска­ние. Более того, очень малая длина дизъюнкций позволяет ис­пользовать сводимости, которые вообще не могли бы быть по­строены для индивидуальных задач с дизъюнкциями большей длины. Это наводит на мысль, что было бы еще лучше, если бы удалось показать, что аналогичная задача 2-ВЫПОЛНИМОСТЬ (каждая дизъюнкция содержит ровно два литерала) является NP-полной. Однако 2-ВЫП может быть решена методом "резо­люций" за время, ограниченное полиномом от произведения числа дизъюнкций и числа переменных заданной индивидуаль­ной задачи (см. также ), и, следовательно, принад­лежит классу Р.

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

7Х7

С прошлого столетия количество таких проблем уменьшилось почти в четыре раза. Когда известный немецкий математик Дэвид Гилберт в самом начале XX века выступил на международном математическом конгрессе в Париже, составленный им список математических и логических задач, которые необходимо было решить в ближайшие сто лет, насчитывал 23 позиции. Плюс еще три проблемы, с которых речь была начата, и которые, будучи уже упомянутыми, не вошли в основной список. Настолько они казались Гилберту само собой разумеющимися.

Всего к концу века было полностью решено 20 проблем. Первой из представленных и последней из решенных стала великая теорема Ферма. Две из оставшихся задач были решены частично, две открыты до сих пор, одна — о математическом описании физических аксиом — признана нематематической, и одна — о прямой, как кратчайшем соединении двух точек, — объявлена слишком расплывчатой, из-за чего невозможно было понять, решена она или нет. Что интересно: все 20 задач были решены совершенно бесплатно. Решение задач Гилберта никакого вознаграждения, кроме вечной научной славы и глубокого научного же удовлетворения, не подразумевало.

Новый список, составленный уже в начале этого века, мировых математических проблем насчитывал всего семь. В отличие от гилбертовского, в нынешнем списке, названном Millennium Prize Problems («Призовые проблемы тысячелетия») за решение каждой из них Математическим институтом Клэя (Clay Mathematics Institute) (Кембридж, Массачусетс, США) была назначена премия в $1 млн. Вернее сказать, наоборот: проблем было выбрано именно семь по числу выделенных на их решение миллионов.

Для справки

Если натянуть на мячик эластичную ленту, то, постепенно стягивая ее, не разрывая и нигде не отрывая от поверхности, можно собрать ее в одну точку. Если же вы натянете такую ленту на бублик, по внешней или внутренней стороне, такой же трюк у вас уже не пройдет. Очень грубо «проблему Пуанкаре» можно сформулировать так: если с некоего предмета можно, как и с мяча, стянуть, не отрывая от поверхности и не разрывая, любую произвольно натянутую эластичную ленту, то у этого предмета нет отверстий. «Проблемой» это утверждение называлось потому, что с момента постановки французским математиком Жюлем Анри Пуанкаре в 1904 году его никто не мог доказать. Между тем, хотя конкретное применение для этого утверждения найти пока сложно, для теоретической математики, в особенности для топологии (раздела математики, изучающего пространственные преобразования), оно очень важно. А пока не было конкретного доказательства, относиться к утверждению следовало весьма осторожным: а что, вдруг Пуанкаре ошибся? Теперь же доверять ему можно смело.

Антитеза

Первый Клэйевский миллион был присужден 18 марта 2010 года 43-летнему российскому математику, сотруднику Санкт-Петербургского отделения Математического института имени Стеклова, Григорию Перельману , решившему так называемую «проблему Пуанкаре».

Считается, что одна из причин, по которой этот питерский математик, которого британская газета The Daily Telegraph поставила на 9 место в списке ста ныне живущих гениев, отказывается общаться с российскими журналистами, — их вопиющая фамильярность и некомпетентность. И это правда. Сплошь и рядом Григория Яковлевича в статьях величают даже не Григорием, а Гришей, а его отцом называют великого популяризатора науки, . При этом авторы статей не удосуживаются даже открыть энциклопедию и выяснить, что Яков Исидорович умер от голода в блокадном Лененграде в 1942 году, а Григорий Яковлевич родился только в 1966, спустя 24 года.

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

После школы перед ним, как перед медалистом, встал тяжелый выбор, куда идти без экзаменов — в Консерваторию или на матмех ЛГУ. Победила страсть к математике. Университет он окончил с отличием. В 1990 году Григорий Яковлевич защитил кандидатскую диссертацию и уехал работать в США, откуда вернулся спустя шесть лет. Тогда же ему присудили премию Европейского математического общества для молодых математиков, однако Григорий Яковлевич отказался ее получать. Работал ведущим научным сотрудником лаборатории математической физики Санкт-Петербургского отделения Математического института им. В. А. Стеклова РАН (ПОМИ), но в 2005 году уволился и почти полностью прервал контакты с внешним миром. А год спустя ему, за решение одной из «Призовых проблем», а именно «проблемы Пуанкаре», была присуждена главная премия среди математиков — «Медаль Филдса» (денежный эквивалент — 15 000 канадских долларов, по сегодняшнему курсу — 432 000 рублей).

Но Перельман отказался и от «Медали Филдса». Два года эксперты проверяли верность его решения. И только в 2010 году ученый совет института Клэя объявил, что ошибок и подтасовок не найдено, и российский математик может приезжать за деньгами. Однако Перельман объявил, что не собирается лететь в Кембридж. От прочих вариантов передачи миллиона долларов он тоже отказался. В одном из немногочисленных интервью он так объяснил свой поступок:

— Я отказался. Вы знаете, у меня было очень много причин и в ту, и в другую сторону. Поэтому я так долго решал. Если говорить совсем коротко, то главная причина — это несогласие с организованным математическим сообществом. Мне не нравятся их решения, я считаю их несправедливыми. Я считаю, что вклад в решение этой задачи американского математика Гамильтона ничуть не меньше, чем мой.

А совсем недавно, в еще одном интервью, Григорий Яковлевич признался:

— Я научился вычислять пустоты, вместе с моими коллегами мы познаем механизмы заполнения социальных и экономических «пустот». Пустоты есть везде. Их можно вычислять, и это дает большие возможности... Я знаю, как управлять Вселенной. И скажите — зачем же мне бежать за миллионом?!

Что в остатке

Как бы там ни было, один миллион уже ушел. Но осталось еще шесть. За что еще их можно получить?

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

«Философским камнем» математики можно назвать уравнения вида x n +y n +z n +.....=t n . Самое простое, — x 2 +y 2 =z 2 (например 3 2 +4 2 =5 2), — полностью исследовал еще за 300 лет до рождества Христова Евклид. Самое знаменитое из подобных уравнений стало основой для теоремы Ферма. А одно из самых больших решений (в докомпьютерную эпоху) предложил в 1769 году Эйлер. Ему удалось соорудить следующее равенство: 2 682 4404 + 15 365 6394 + 18 796 7604 = 20 615 6734. Универсального метода вычисления для подобных уравнений не существует. Однако известно, что у каждого из них может быть либо конечное, либо бесконечное число решений. Математики Берч и Свинертон-Дайер в 1960 году создали метод, по которому каждое такое уравнение можно свести к более простому, называемому дзета-функцией. По их выведенному экспериментальным путем, но теоретически не доказанному предположению, если эта функция в точке 1 будет равна 0, то количество решений искомого уравнения будет бесконечным. В противном случае, их либо вообще не будет, как в случае с теоремой Ферма, либо их будет какое-то ограниченное количество. Ни доказать, ни опровергнуть это утверждение пока никто не смог.

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

Исследовать объект тем сложнее, чем сложнее он устроен. Поэтому математики обычно сначала пытаются разложить его на объекты более простые, работать с которыми, как понятно, проще. Проблема в том, что просто разложить объект на составляющие получается далеко не всегда. Иногда при этом возникают новые части, неизвестно откуда взявшиеся и непонятно что из себя представляющие. Либо, наоборот, при более детальном исследовании выясняется, что каких-то деталей явно не хватает. Проще говоря, исследуя просто кирпичи, мы не можем себе представить, что собой представляет составленный из них дом, как он выглядит, и по каким правилам его строят. Для этого нужно, как минимум, изучить еще и заключенное между ними пустое пространство комнат. Профессор Кембриджа Вильям Ходж в своих трудах в 1941 году описал условия, при которых, как ему кажется, такие непонятные «лишние» части не могут возникать и в которых любое геометрическое тело можно исследовать как алгебраическое уравнение, составив его математическую модель. Ни доказать его предположение, ни опровергнуть его ученые не могут уже 70 лет.

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

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

Проблема Решения-Проверки (Проблема Кука-Левина)

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

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

Среди всей массы чисел особое место занимают числа, которые невозможно разделить ни на что-то более мелкое, чем они сами: 1, 2, 3, 5, 7, 11, 13, 17 и так далее. Такие числа называются «простыми» и они для математиков крайне важны. Как они распределяются по числовому ряду — пока известно одному Богу. Риман в 1859 году даже не предложил способ их поиска или проверки. Проверить, является ли число «простым» или нет, можно только попробовав разделить его на все меньшие числа (самое большое из известных на сегодняшний день «простых» было найдено в августе 2008 года и состоит из 12 978 189 цифр). Он просто нашел метод, по которому можно определить максимальное количество простых чисел, не превышающих некое заданное число. На сегодня математики проверили этот метод с полутора триллионами «простых». Сбоев пока найдено не было. Однако это вовсе не говорит о том, что метод не споткнется на полтора триллиона первой проверке. А, поскольку гипотеза Римана, перешедшая в новый список еще из списка Гилберта, активно используется для расчета систем безопасности передачи данных — в сотовых сетях, в сети Интернет и так далее, — ее доказательство имеет весьма практический смысл. И миллион здесь платить есть за что.

Уравнения Янга-Миллса

Свои квантовые уравнения американские физики Чжэнь-Нин Янг и Роберт Миллс составили в 1954 году, наблюдая за движением элементарных частиц. Выведенные почти на чистой интуиции они, тем не менее, замечательно описывают почти все виды их взаимодействий. С помощью уравнений даже было предсказано открытие новых частиц, которые потом были действительно найдены физиками-ядерщиками крупнейших мировых лабораторий — Brookhaven, Stanford и CERN. Правда, с помощью теории Янга-Миллса невозможно правильно предсказать массу частиц, однако, несмотря на это, уравнениями смело пользуются почти все ядерщики мира. Хотя до сих пор непонятно, как они работают и, вообще, так ли уж они верны. Из всех вышеперечисленных уравнений эти — наиболее сложные, поэтому мы их приводить не будем. Но, если вам не хватит пяти миллионов, которые можно получить за решение предыдущих пяти проблем, никто вам не запретит постараться решить еще и эту. Дерзайте — и обрящете.

А может, подождать?

Фамилию Перельмана сейчас помнит весь цивилизованный мир. А вот кто такой Эндрю Уайлс знают лишь специалисты. Но ведь это именно он в 1995 году исполнил многовековую мечту математиков — доказал сформулированную еще в 1637 году Великую теорему Ферма. За ее решение в 1908 году тоже была объявлена специальная премия в 100 000 немецких марок, что для начала прошлого века было чрезвычайно много. Однако две мировых войны и связанная с ними инфляция весьма сильно ее урезали. Настолько, что математик получил за свой труд чисто символическую сумму, примерно эквивалентную 15 долларам. А подождал бы Уайлс с публикацией своего доказательства лет 6-7, теорему Ферма обязательно включили бы в «Призовые проблемы тысячелетия» и оценили бы в миллион. И тогда математик стал бы очень богатым. Или очень знаменитым. Как Григорий Перельман.