4886
Луганський професор опублікував рішення однієї з 7-ми математичних задач тисячоліття
Професор кафедри "Комп'ютерні системи та мережі" Східноукраїнського національного університету імені Володимира Даля Анатолій Плотніков запропонував і опублікував в міжнародному науковому журналі "Journal of computer science" (8 том, 7 випуск) варіант вирішення раніше невирішеної математичної задачі "P vs NP" ("Клас задач Р проти класу задач NP").
Як повідомляється на сайті університету, кілька років тому Плотніков уже пропонував світовому співтовариству математиків варіант рішення завдання "P vs NP", однак виявлений контрприклад вказав на приватний характер рішення. Тому він продовжив роботу над пошуком спільного рішення даної задачі міленіуму.
Суть проблеми "P vs NP" полягає в пошуку можливого рішення задач класу NP за допомогою хороших алгоритмів (тобто, за невеликий проміжок часу). Клас NP включає в себе всі завдання, які вирішуються на комп'ютері. Вони мають велику практичну значимість, однак доказ того, що багато з них можуть бути вирішені за допомогою хорошого алгоритму, не існує. Клас задач Р, що входить до NP, навпаки, можна вирішити за допомогою хорошого алгоритму.
Плотніков зазначає, що процес вирішення завдань класу NP розтягнутий за часом, а в процесі вирішення з'являються проміжні результати. Професор визначає підклас UF завдань NP, у яких проміжні результати можна знайти за невеликий час, залежно від розмірності задачі. Так як ця властивість у визначенні класу NP не обумовлюється, то в нього можуть входити завдання, для яких перевірка проміжного результату може вимагати неприйнятно великого часу. Плотніков у своєму рішенні вказує, що UF не дорівнює NP, а Р входить в UF. Отже, Р не дорівнює NP.
Завдання міленіуму (Millennium Prize Problems) складають сім математичних проблем, охарактеризованих як "важливі класичні задачі, рішення яких не знайдено от уже протягом багатьох років". За вирішення кожної з цих проблем Інститутом Клея запропонований приз 1 мільйон доларів. Анонсуючи приз, інститут Клея провів паралель зі списком проблем Гільберта, представленим в 1900 році, що мав істотний вплив на математиків XX століття. З 23 проблем Гільберта більшість вже вирішені, і тільки одна - гіпотеза Рімана - увійшла до списку завдань міленіуму. До цих пір вирішена тільки одна з семи проблем тисячоліття (гіпотеза Пуанкаре): в 2002-2003 роках її вирішив російський математик Григорій Перельман, який потім відмовився від мільйона доларів.
За матеріалами: Дзеркало Тижня
Поділитися новиною
