Рівність класів P і NP

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

Проблеми тисячоліття
Рівність класів P і NP
Гіпотеза Годжа
Гіпотеза Пуанкаре*
Гіпотеза Рімана
Квантова теорія Янга — Мілса
Рівняння Нав'є — Стокса
Гіпотеза Берча і Свіннертона-Даєра
* доведені

Класи P і NP

Зрештою, проблема P = NP полягає в наступному: якщо позитивну відповідь на якесь питання можна швидко перевірити (за поліноміальний час), то чи правда, що відповідь на це ж питання можна швидко знайти (за поліноміальний час і використовуючи поліноміальну пам'ять)?

Наприклад, чи є істинним твердження, що серед чисел (-2, -3, 15, 14, 7, -10, …) є такі, що їхня сума дорівнює 0 (задача про суми підмножин)? Відповідь так, тому що -2 -3 + 15 -10 = 0 легко перевірити за допомогою кількох додавань (інформацію, необхідну для перевірки позитивної відповіді, називають сертифікатом).

Чи випливає звідси, що так само легко підібрати ці числа? Перевірити сертифікат так само легко, як знайти його? Здається, що підібрати числа складніше (не доведено).

Відповідь на питання про рівність класів P і NP визначила б, чи дійсно завдання легше перевірити, ніж вирішити (P ≠ NP). Або вирішити настільки ж просто, як і перевірити (P = NP).

Це можна застосовувати до всіх подібних задач, а не тільки до задачі про суми підмножин. Також цей принцип може бути застосований до задач, відповідь на які складніша, ніж ТАК чи НІ.

Відносини між класами P і NP розглядаються в теорії обчислювальної складності (розділу теорії алгоритмів,) що вивчає ресурси, необхідні для вирішення деякої задачі. Найзагальніші ресурси — це час (скільки потрібно зробити кроків) і пам'ять (скільки пам'яті потрібно для вирішення задачі).

Історія

З визначення класів P і NP відразу випливає наслідок: ${\displaystyle P\subseteq NP}$. Проте досі нічого не відомо про строгість цього включення, тобто чи існує алгоритм, який лежить в NP, але не лежить в P. Якщо такого алгоритму не існує, то всі завдання, що належать класу NP, можна буде вирішувати за поліноміальний час, що обіцяє величезну вигоду з обчислювальної точки зору. Зараз найскладніші NP-задачі (так звані NP-повні задачі) можна вирішити за експоненційний час, що майже завжди є неприйнятним.

Вперше питання про рівність класів було поставлено незалежно Куком і Левіним у 1971 р. На сьогоднішній день більшість математиків вважають, що ці класи не рівні. Згідно з опитуванням, проведеним у 2002 р. серед 100 вчених, 61 людина вважає, що відповідь — «не рівні», 9 — «рівні», 22 не змогли відповісти і 8 вважають, що гіпотеза не виводиться з поточної системи аксіом і, таким чином, не може бути доведена або спростована.

Зараз проблема рівності класів P і NP є однією із семи проблем тисячоліття, за вирішення якої Математичний інститут Клея призначив премію в мільйон доларів США.

Спроби довести

У серпні 2010 року американський дослідник з HP Labs Вінай Деолалікар (англ. Vinay Deolalikar) надіслав деяким вченим на перевірку своє доведення нерівності P ≠ NP. Стівен Кук назвав його препринт «відносно серйозною спробою вирішення проблеми P проти NP».

Великий список публікацій, автори яких заявляють, що довели або спростували рівність класів, можна знайти на сторінці Ph.D. Gerhard J Woeginger з технологічного університету Ейндховена, Нідерланди.

Примітки

1. The P-versus-NP page.

Див. також

• Відкриті математичні проблеми

Посилання

• С. Кук (англ.)
• С. Ніколєнко Компьютерра, 2006. (рос.)
• Н. П. Варновскій. Проблема P =? NP, класи складнощів і криптографія. 2005. (рос.)
• Прітикін Ю. Л. Что такое проблема P vs. NP? VIII літня школа «Сучасна математика». Дубна, 2008 (рос.)
• А. А. Разборов P? = NP або проблема перебору: погляд з 90-х. (рос.)
• Gerhard J. Woeginger. The P-versus-NP page. (англ.) Список посилань на запропоновані «вирішення» даної проблеми. Деякі з них стверджують рівність P і NP, деякі — зворотне.
• Vinay Deolalikar P ≠ NP (англ.) Попередня версія статті Vinay Deolakikar.