Рівність класів 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 відразу випливає наслідок: 
. Проте досі нічого не відомо про строгість цього включення, тобто чи існує алгоритм, який лежить в NP, але не лежить в P. Якщо такого алгоритму не існує, то всі завдання, що належать класу NP, можна буде вирішувати за поліноміальний час, що обіцяє величезну вигоду з обчислювальної точки зору. Зараз найскладніші NP-задачі (так звані NP-повні задачі) можна вирішити за експоненційний час, що майже завжди є неприйнятним.
Вперше питання про рівність класів було поставлений незалежно Куком і Левіним у 1971 р. На сьогоднішній день більшість математиків вважають, що ці класи не рівні. Згідно з опитуванням, проведеним у 2002 р. серед 100 вчених, 61 людина вважає, що відповідь — «не рівні», 9 — «рівні», 22 не змогли відповісти і 8 вважають, що гіпотеза не виводиться з поточної системи аксіом і, таким чином, не може бути доведена або спростована.
Зараз проблема рівності класів P і NP є однією із семи проблем тисячоліття, за вирішення якої Математичний інститут Клея призначив премію в мільйон доларів США.
Спроби довести [ред.]
У серпні 2010 року, американский дослідник Vinay Deolalikar надіслав деяким вченим на перевірку своє доведення нерівності P ≠ NP. Стівен Кук назвав його препринт «відносно серйозною спробою вирішення проблеми P проти NP».
У 2012 році український професор Анатолій Плотніков опублікував свій варіант вирішення в журналі Journal of computer science. Раніше йому вдалося вирішити цю задачу для окремого випадку. Поточне рішення претендує на загальне і в даний час проходить перевірку[1].
Див. також [ред.]
Посилання [ред.]
- С. Кук Офіційний опис проблеми (англ.)
- С. Ніколєнко «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.
