Сергей Фаер. Траблшутинг. Как решать нерешаемые задачи, посмотрев на проблему с другой стороны

Равенство классов p и np

Если остальные «Задачи тысячелетия» относятся к чисто математическим, то эта имеет отношение к актуальной теории алгоритмов. Проблема, касающаяся равенства классов р и np, известная также, как проблема Кука-Левина, понятным языком может быть сформулирована следующим образом. Предположим, что положительный ответ на некий вопрос можно проверить достаточно быстро, т. е. за полиномиальное время (ПВ). Тогда правильно ли утверждение, что ответ на него можно довольно быстро отыскать? Еще проще эта задача звучит так: действительно ли решение задачи проверить не труднее, чем его найти? Если равенство классов р и np будет когда-либо доказано, то все проблемы подбора можно будет решать за ПВ. На данный момент многие специалисты сомневаются в истинности этого утверждения, хотя не могут доказать обратное.

Вопреки вердикту

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

читайте также–>–>Математики рассчитали, как дальше будет развиваться эпидемия коронавируса

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

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

С тех пор о головоломке, некогда занимавшей лучшие математические умы, забыли. Ляля Гиззатовна искала “ключ” несколько лет и, перепробовав множество путей, нашла простое и блестящее решение, к которому, судя по оставшимся в истории записям, шел сам Архимед, но довести его до конца не сумел.

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

Последние три сотни лет решение даже не искали, а все это время математика шла семимильными шагами. Возможно, стоит попробовать снова?

Более того, автор геометрического подхода уверена: откладывая на биссектрисе нужное число радиусов, угол можно разделить не только на три, но и на пять, семь и девять частей – другими словами, разделить его на любое нечетное число. А это, в свою очередь, позволит найти решение еще одной математической головоломки – вписать в окружность любой правильный многоугольник. В справочниках до сих пор утверждается, что вписать правильные многоугольники, имеющие семь и девять сторон, в окружность невозможно. Ну разве это не открытие?

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

Задача Берча — Свиннертон-Дайера

К категории «Нерешенные задачи» относится и гипотеза, предложенная английскими учеными из Кембриджского университета. Еще 2300 лет назад древнегреческий ученый Эвклид дал полное описание решений уравнения x2 + y2 = z2.

Если для каждого из простых чисел посчитать количество точек на кривой по его модулю, получится бесконечный набор целых чисел. Если конкретным образом «склеить» его в 1 функцию комплексной переменной, тогда получится дзета-функция Хассе-Вейля для кривой третьего порядка, обозначаемая буквой L. Она содержит информацию о поведении по модулю всех простых чисел сразу.

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

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