Рівність класів 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 відразу випливає наслідок: $P\subseteq NP$. Проте досі нічого не відомо про строгість цього включення, тобто чи існує алгоритм, який лежить в NP, але не лежить у P. Якщо такого алгоритму не існує, то всі задачі, що належать класу NP, можна буде розв'язати за поліноміальний час, що обіцяє величезну вигоду з обчислювальної точки зору. Зараз найскладніші NP-задачі (так звані NP-повні задачі) можна розв'язати за експоненційний час, що майже завжди є неприйнятним.

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

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

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

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

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

Див. також

• Відкриті математичні питання

Посилання

• С. Кук Офіційний опис проблеми (англ.)
• С. Ніколєнко "P =? NP ". Компьютерра, 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.