Прислала
Нелли Шестопалова
Фото: Fotolia/PhotoXPress.ru
Математик из Челябинска, возможно, нашел решение одной из задач тысячелетия, над которой бьются ученые вот уже много лет. Южноуралец намерен отправить результаты своего исследования в Математический институт Клэя. Если расчеты окажутся верными, он получит солидную премию — миллион долларов.
Челябинский математик Анатолий Панюков уже 30 лет занимается решением одной из сложнейших задач тысячелетия. А именно — проблемой равенства классов P и NP. За ее решение американский Математический институт Клэя обещал премию 1 млн долларов. Решить математическую задачу пытается не только челябинский ученый. На сегодняшний день существует более 100 вариантов ее решения, но ни один из них пока не признан верным.
Большинство ученых считают, что P не равно NP. Однако, если я рассчитал все правильно, то P будет равным NP. Результат считается правильным, если ему нет опровержения. Свои выкладки я обсуждал с коллегами, посмотрим, какой ответ будет из Математического института Клэя.
Суть вопроса равенства P и NP заключается в следующем. Есть некая задача, ответ на которую занимает тем больше времени, чем сложнее задача. Правда ли, что проверить решение задачи не легче, чем его отыскать? Например, верно ли, что среди чисел {−2, −3, 15, 14, 7, −10, …} есть такие, что их сумма равна 0? Ответ: да, потому что (−2) + (−3) + 15 + (−10) = 0 проверяется несколькими сложениями. Следует ли отсюда, что так же легко подобрать эти числа? Большинство математиков считают, что подобрать числа сложнее. А вот Анатолий Панюков, возможно, доказал обратное.
Справка SmartNews
Семь задач тысячелетия — это проблемы, решения которых не могут быть найдены в течение многих лет. За решение каждой из них Математическим институтом Клэя предложен приз 1 млн долларов. В настоящее время доказана только одна задача — гипотеза Пуанкаре, решить ее удалось Григорию Перельману, однако тот от премии отказался. Деньги в результате отдали Институту Анри Пуанкаре.
Видео
Что доказал Григорий Перельман?
Видео: djstanfx/YouTube.
Перельман молодец, прославил нашу страну и показал, что еще есть ученые со своими твердыми принципами, каждый из нас бы не отказался от миллиона долларов, но он гений, а это люди другого склада.
Это очень важная задача для криптографии, науки об использовании математики для шифрования данных. Если P не равно NP, это значит, что многие алгоритмы стойкие. Что такое стойкие алгоритмы? Это значит, что шифр очень сложно раскрыть постороннему лицу, для этого нужны большие вычислительные ресурсы. Если же P равно NP, это значит, что можно и нужно разрабатывать новые методы шифрования.
Если равенство P и NP окажется верным, это может привести к настоящей революции в информатике. Как говорят эксперты, современная практическая криптография окажется бесполезной. А ведь именно эти алгоритмы защищают, к примеру, банковские карты.
— Большинство ученых считает, что эти классы не равны, и именно на этом неравенстве и построены многие современные асимметричные криптографические алгоритмы, относимые к классу NP. Доказательству челябинского математика еще только предстоит проверка, и вполне может оказаться так, что 30 лет его исследований тоже ошибочны. А что если на секунду представить, что Анатолий Панюков прав? Ведь тогда современной криптографии придет конец. По крайней мере, ее коммерческой составляющей. И останется нам перейти на шифр Вернама, обладающий абсолютной криптографической стойкостью. Собственно, к чему эта заметка? А к тому она, чтобы задаться вопросом: «А что если?». Есть ли у нас (у криптографов, у регулятора, у производителей, у потребителей) резервный план на случай доказательства P = NP? Что мы будем делать, если это действительно так и такое доказательство найдет практическое применение в криптографии? У меня ответа пока нет.
Справка SmartNews
Анатолий Панюков — профессор, завкафедрой экономико-математических методов и статистики на факультете вычислительной математики и информатики. Он автор более 200 научных и учебных публикаций и более 20 изобретений. Имеет звания «Заслуженный работник высшей школы РФ», «Почетный работник высшего профессионального образования», «Изобретатель СССР», награжден медалью Минвуза СССР и Почетной грамотой губернатора Челябинской области.
Прислал
Сергей Ягунов
Отечественные математики всегда были востребованными специалистами за рубежом. Как ни крути, математика требует большого ума и логики, а умных людей всегда мало. Нужно беречь отечественную школу математиков.
Виктор Загвоздин
Pciha
Валерий Черняев
Сергей Ягунов
Тарас Алюшников
Павел Юдкин
анатолий кульбацкий
9 комментариев к материалу. Показать отмеченные редакциейвсе