Анатолій Плотніков запропонував власний розв’язок проблеми «P vs NP»

Після виходу цієї публікації у 2012 році, редакція порталу “Моя наука” отримала аргументовані коментарі математика Володимира Некрашевича, професора факультету математики Техаського університету A&M (США), який займається комбінаторною теорією груп та функціональним аналізом, який стверджував, що про жодне відкриття у роботі Плотнікова не йдеться. Редакція запросила для оцінки статті ще одного спеціаліста — доктора Олега Лісового, викладача математики Університету Франсуа Раблє в Турі (Франція),  який підтвердив висновки професора Некрашевича. На жаль, під час переїзду на нову платформу коментарі спеціалістів було втрачено. Пізніше до двох експертів доєдналася старший науковий співробітник Інституту математики НАН України Ірина Єгорченко. Спираючись на думку експертів як на позицію наукової спільноти, “Моя наука” однозначно повідомляє, що жодного відкриття професор Плотніков не здійснив. Тим не менш, ця стаття містить виклад самої проблеми та введення до криптології, яке є достовірним та цікавим.

---

За вирішення математичної проблеми дають мільйон доларів. Неймовірний приз для математика, але ще неймовірніше відмова від такого виграша. Тим не менш, російський математик Григорій Перельман у 2010 році саме так і зробив: після доведення гіпотези Пуанкаре проігнорував винагороду. Тепер математичний світ слідкує за іншим претендентом на перемогу — український вчений Анатолій Плотніков запропонував власний розв’язок іншої важливої проблеми “P проти NP”. Ця задача має не лише теоретичне значення, але й відкриває нові можливості для розвитку криптології.

Криптологія – це наука, що вивчає теоретичні проблеми захисту інформації. В рамках неї виділяють дві дисципліни: криптографію, що займається проблемами ефективного шифрування, та криптоаналіз, що ставить задачу розшифрування інформації в умовах відсутності доступу до ключа – спеціального алгоритму, що дозволяє читати зашифрований текст.

Вигляд самого процесу припускається такий. Аліса прагне передати деяку закриту інформацію Бобу засобами телекомунікації. Оскільки інформація може бути перехоплена, то використовується шифрування. Таке шифрування включає в себе алгоритм шифрування, що дозволяє перетворити текст у вигляд, до якого ставиться вимога недоступності безпосереднього прочитання, і алгоритм дешифрування, що дозволяє перетворити зашифрований текст у початковий вигляд. Часто розкриття цих алгоритмів зводиться до пошуку деякого набору символів («слова»), який також називають ключем. Крім того, нині популярністю володіє RSA-шифр, що є «шифром з відкритим ключем». Особливістю таких шифрів є те, що зашифрувати інформацію може будь-хто (набір символів – «відкритий ключ», що дає змогу зашифрувати інформацію, не тримається у таємниці), але розшифрувати можна тільки з допомогою «таємного ключа», який не розголошується.

Важливою вимогою до шифрування є стійкість до зламу. Для систем шифрування з відкритим ключем це означає, що на основі відкритого ключа, навіть якщо відомо, як він отримується із закритого, неможливо швидко знайти останній. Для цього вибирають таку функцію f, щоб за відомого слова x пошук y=f(x) займав значно менше часу, ніж пошук x за відомого y. Після цього вибирають слово x настільки довгим, наскільки це можливо, рахують y=f(x) і оголошують y відкритим ключем.

Наприклад, при шифруванні з допомогою RSA береться пара досить великих простих чисел (чисел, що діляться націло лише на 1 та на себе), і шукається їх добуток. У вигляді відкритого ключа подається знайдений добуток і деяке допоміжне число, а закритим ключем називають цей самий добуток і інше допоміжне число, що можна знайти (при чому досить легко) тільки за умови знання вихідної пари простих чисел. Таким чином, для зламу шифру потрібно розкласти число у добуток двох простих, що є складною задачею. Натомість, пошук добутку двох простих чисел є задачею значно простішою.

Поняття складності задач допускає формалізацію. При цьому вводять поняття «мови», а задачу ставлять у вигляді задачі виявлення належності «слова» «мові» (задачі розпізнавання). Надалі будуть введені неформальні означення, що стосуються складності задач.

Класс задач розпізнавання (належності слів мові), пошук слів в яких може бути виконаний за поліноміальний час з використанням Машини Тьюрінга, називається P-класом.

Класс задач розпізнавання, перевірка слів в яких може бути виконана за поліноміальний час з використанням Машини Тьюрінга, називається NP-класом.

В якості машини Тьюрінга, як це слідує з тезису Черча, можна брати будь-який алгоритм в інтуїтивному розумінні (наприклад, реалізований на одній із відомих мов програмування).

Поліноміальний час означає, що кількість операцій, потрібних для розв’язання задачі, не більше, ніж значення деякого многочлена, знайденого від довжини слова. На противагу поняттю поліноміального часу використовується поняття експоненціального часу. Наприклад, перебір всіх чисел від 1 до n виконується за експоненціальний час, оскільки потребує n операцій для слова довжини не більше, ніж 1+lg n, якщо воно записане у десятковій системі числення. Крім того, за експоненціальний час розв’язується задача виявлення простоти натурального числа за класичним алгоритмом.

Очевидно, що клас P не більше, ніж клас NP (тобто, перевірити розв’язок не складніше, ніж знайти його). Гіпотеза про рівність класів P та NP означає, що будь-яка задача, що допускає перевірку розв’язку за поліноміальний час, допускає також за поліноміальний час і його пошук. Якщо гіпотеза вірна, то це означає, що всі шифри з відкритим ключем потенціально знаходяться під загрозою, а дослідження у цьому напрямі будуть носити відчутно меншу цінність.

Ця проблема включена у оголошений у 2000 році приватною некомерційною організацією Інститутом математики ім. Клея (Кембрідж, Масачусетс, США) перелік «проблем тисячоліття», за розв’язання кожної з яких пропонується винагорода в 1 мільйон доларів США. Список включає 7 проблем, одна з яких (гіпотеза Пуанкаре) вже була вирішена раніше Г.Я. Перельманом у 2006 році.

У серпні 2012 року кандидат технічних наук, професор Східноукраїнського національного університету ім. Даля (Луганськ) Анатолій Плотніков опублікував варіант розв’язання математичної задачі “P проти NP” у журналі Journal of Computer Science (2012; V. 8, № 7, p. 1036-1040). Отриманий результат полягає в тому, що гіпотеза рівності класів невірна.

У резюме до своєї статті автор повідомляє про методологічні проблеми у визначенні класу NP та обговорює введення проміжного класу із назвою UF, що містить клас P, але водночас міститься у класі NP, не співпадаючи з ним.

Більш детально розв’язок виглядає таким чином.

Було уточнено означення класу NP, стосовно якого додатково припускається, що кількість символів розв’язку задачі залежить поліноміально від кількості вхідних символів.

Надалі вводиться допоміжний клас систем множин, «системи наслідування», що містять разом із деякою множиною всі її підмножини, і у термінах цього класу формулюються задачі розпізнавання.

З допомогою поняття поетапного (поелементного) пошуку розв’язку вводиться клас задач UF, для розв’язання кожного етапу яких потрібен поліноміальний час. Всі інші задачі оголошуються «задачами з експоненціальною природою».

Оскільки UF містить P, а NP містить UF, то для спростування гіпотези достатньо показати, що NP не співпадає з UF. При доведенні цього моменту стверджується, що в NP, на відміну від UF, входять задачі з експоненціальною природою, а тому класи не співпадають.

Разом з тим, у роботі не вказується явно, чому слід вважати, що клас задач з експоненціальною природою не є порожнім, тому можна очікувати, що дискусії навколо роботи продовжаться.

Також варто відзначити, що дослідженню цієї проблеми присвячено чимало робіт найбільш різного рівня з авторством, представленим усім спектром від дилетантів до професорів. Але дану роботу виділяє з поміж інших те, що вона опублікована у рецензованому науковому виданні*. Так чи інакше, її доля буде вирішена у подальшому обговоренні.

On the Relationship between Classes P and NP
Anatoly D. Plotnikov, 2012.

---

• Журнал Journal of Computer Science є низькоцитованим та маловідомим виданням, серед редакційної колегії якого нема відомих у світі математиків (Моя наука).