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

Анатолий Плотников занимается проблемами информатики и дискретной математики с
Суть проблемы «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 проблем Гильберта большинство уже решены, и только одна — гипотеза Римана — вошла в список задач миллениума. До сих пор решена только одна из семи проблем тысячелетия (гипотеза Пуанкаре): в
A | A | A |
Оценка материала: | (1) |
Чтобы оставить комментарии, вы должны быть авторизованы.
Код для вставки:
-
14 марта, 14:36
Ушел из жизни легендарный английский физик-теоретик Стивен Хокинг -
31 января, 13:37
Билингвизм задерживает наступление болезни Альцгеймера -
17 января, 12:49
Новосибирские ученые обнаружили ген депрессии -
15 февраля, 19:59
Ученые рассказали, каким будет мир через 100 лет -
22 сентября, 12:44
Москву с лекцией посетит всемирно известный египтолог доктор Захи Хавасс
-
14 марта, 10:03
Стивен Хокинг. «Живая легенда» науки о скорой гибели человечества -
12 августа, 18:45
Антинаучная статья -
16 декабря, 17:13
11 важных фактов об управлении IT. Часть вторая -
24 февраля, 09:09
Образование будущего. Продолжение -
10 февраля, 13:39
Образование будущего
На данный момент нет комментария к этому материалу.