Самая сложная задача в мире. Ферма. Великая теорема Ферма

Такие методы, как решето Эратосфена, могут быть более или менее сложными. Изучение эффективности алгоритма вычислений является одной из самых важных ветвей исследования в науке о вычислениях. Появляются неразрешимые проблемы, если не существует алгоритма, который мог бы дать ответ. При этом мы можем оценить, за какое максимальное время решается проблема при заданном алгоритме. Это можно обозначить как O(f(n)), где f(n) — любая функция от n, которая, в свою очередь, является мерой "размера" проблемы (например, это может быть число элементов в списке). Могут быть алгоритмы, обладающие сложностью: O(n), O(n²), O(log n), O(nlog n), O(eⁿ) и так далее. С другой стороны, существуют проблемы, которые хоть и разрешимы, но требуют столько времени, что нереально пытаться их решить. Это проблемы экспоненциальной сложности — O(eⁿ) — или, что еще хуже, комбинаторной сложности — O(n!): например, посчитать все перестановки п объектов. Они получают название неразрешимых проблем. Есть и другой очень интересный класс проблем: те, что могли бы быть неразрешимыми, но мы не знаем, так ли это. По сути это проблемы, для которых очень легко проверить верность решения, если оно известно, но нахождение решения кажется неразрешимой проблемой. Мы говорим "кажется", поскольку никто не смог доказать, так ли это. Они называются проблемами NP. Проблема разложения числа на простые множители — самый важный пример для нас. Наконец, существуют разрешимые проблемы: мы знаем, что они решаемы в разумное, известное как полиномиальное, время. Это проблемы порядка O(n^k), O(n log n) или O(log n). Решето Эратосфена — это алгоритм сложности Ο(10^√N), явно экспоненциальной.

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

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

В переписке через Мерсенна Френикль бросил Ферма вызов, предлагая найти совершенное число из 20 знаков. Ответ от тулузского математика поступил немедленно: не существует такого числа, как и нет такого числа из 21 знака, и это, в свою очередь, доказывает, что гипотеза о существовании по крайней мере одного совершенного числа в каждом интервале между 10ⁿ и 10ⁿ⁺¹ ложная.