Print

Математик зі СНУ ім. В. Даля вирішив одну із задач міленіуму

 

 Професор кафедри «Комп’ютерні системи та мережі» Східноукраїнського національного університету імені Володимира Даля Анатолій Плотніков запропонував та опублікував в міжнародному науковому журналі «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 роках її вирішив російський математик Григорій Перельман.

Підготувала: Наталія Осичнюк