Професор кафедри «Комп'ютерні системи та мережі» Східноукраїнського національного університету імені Володимира Даля Анатолій Плотніков запропонував і опублікував в міжнародному науковому журналі «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 роках її вирішив російський математик Григорій Перельман, який потім відмовився від мільйона доларів. !zn
Читайте також:
Оголошено лауреатів «математичного Нобеля»
Математична освіта в Україні переживає занепад: тільки 12% дев'ятикласників добре знають математику