Профессор ВНУ им. В. Даля решил одну из задач миллениума

Профессор кафедры «Компьютерные системы и сети» ВНУ им. В. Даля Анатолий Плотников предложил и опубликовал в международном научном журнале «Journal of computer science» (8 том, 7 выпуск) вариант решения ранее нерешенной математической задачи «P vs NP» ( «Класс задач Р против класса задач NP»).

 <

Анатолий Плотников занимается проблемами информатики и дискретной математики с 80-х годов. Несколько лет назад Далевский ученый уже предлагал мировому сообществу математиков вариант решения задачи «P vs NP», но обнаружен контрпример указал на частный характер его решения. Поэтому Анатолий Дмитриевич продолжил работу над поиском совместного решения данной задачи миллениума.

Суть проблемы «P vs NP» заключается в поиске возможного решения задач класса NP с помощью хороших алгоритмов (т.е. за небольшой промежуток времени). Класс NP включает в себя все задачи, которые решаются на компьютере. Они имеют большую практическую значимость, однако доказательство того, что многие из них могут быть решены с помощью хорошего алгоритма, не существует. Класс задач Р, входящий в NP, наоборот, можно решить с помощью хорошего алгоритма.
Анатолий Плотников отмечает, что процесс решения задач класса NP растянут по времени, а в процессе решения появляются промежуточные результаты. Профессор определяет подкласс UF задач NP, в которых промежуточные результаты можно найти за небольшое время, в зависимости от размерности задачи. Это свойство в определении класса NP не указывается, поэтому в него могут входить задачи, для которых проверка промежуточного результата может потребовать неприемлемо длительного времени. Анатолий Дмитриевич в своем решении указывает, что UF не равно NP, а Р входит в UF. Следовательно, Р не равно NP.

Решение задачи «P vs NP» имеет важное практическое значение. В частности, оно позволяет определить пути преодоления многих проблем криптологии - науки, занимающейся методами шифрования и дешифрования информации, - что поможет защитить важную информацию с ограниченным доступом (банковскую, военную, коммерческую тайну). Также полученный ответ можно использовать и в других областях знаний.
На данном этапе вариант решения, предложенного Анатолием Плотниковым, проходит проверку. Однако, независимо от результата, Далевский ученый не собирается останавливаться на достигнутом: «Существует проблема решения задач класса UF, и я планирую работать в этом направлении. Я не прекращу работать в этой области, ведь это моя жизнь».

Напомним, что задачи миллениума (Millennium Prize Problems) составляют семь математических проблем, охарактеризованных как «важные классические задачи, решение которых не найдено вот уже в течение многих лет». За решение каждой из них Институтом Клэя предложен приз в 1 000 000 долларов США. Анонсируя приз, институт Клэя провел параллель со списком проблем Гильберта, представленным в 1900 году, который существенно повлиял на математиков XX века. Из 23 проблем Гильберта большинство уже решены, и только одна - гипотеза Римана - вошла в список задач миллениума.

До сих пор решена только одна из семи проблем тысячелетия (гипотеза Пуанкаре): в 2002-2003 годах ее решил российский математик Григорий Перельман.