Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



План:


Введення

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

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


1. Класи P і NP

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

Неформально кажучи, чи справді вирішення завдання легше перевірити, ніж відшукати?

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


2. Зміст проблеми

Діаграма класів складності за умови PNP.

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


3. Історія

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

Вперше питання про рівність класів було поставлено Стівеном Куком в 1971 і незалежно Леонідом Левіним в 1973. [1]

В даний час більшість математиків вважають, що ці класи не рівні. Згідно з опитуванням, проведеним в 2002 серед 100 вчених, [2] 61 людина вважає, що відповідь - "не рівні", 9 - "рівні", 22 не змогли відповісти і 8 вважають, що гіпотеза не виведена з поточної системи аксіом і, таким чином, не може бути доведена або спростована.


4. Спроби докази

6 серпня 2010 [3] співробітник дослідницької лабораторії Hewlett-Packard в Пало-Альто Віней Деолалікар (англ.) розіслав деяким вченим на перевірку свій доказ нерівності P і NP. [4] Стівен Кук назвав його препринт "щодо серйозною спробою вирішення проблеми P vs NP". [5] Проте вже в тому ж місяці були знайдені недоліки в доказі. Деолалікар заявив, що в наступній версії доказ він постарається врахувати всі зауваження. [3] [6]

На вікістраніце "Deolalikar P vs NP paper", пов'язаної з проектом Polymath, наводиться критичний аналіз, зібрані передбачувані помилки і деякі помилки в роботі Деолалікара. [7] Там же можна прослідкувати за онлайн-реакцією на запропоноване доказ.


Примітки

  1. Stephen Cook. The Importance of the P versus NP Question - www.cs.toronto.edu/ ~ sacook / homepage / JACMpvsnp.ps.
  2. William I. Gasarch (2002). " The P =? NP poll. - www.cs.umd.edu/ ~ gasarch / papers / poll.pdf ". SIGACT News 33 (2): 34-47. DOI : 10.1145/1052796.1052804 - dx.doi.org/10.1145/1052796.1052804.
  3. 1 2 Lenta.ru - Повз - lenta.ru/articles/2010/08/18/fail /
  4. Vinay Deolakikar. P ≠ NP - www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf. preprint.
  5. P ≠ NP-Greg and Kat's blog - gregbaker.ca/blog/2010/08/07/pn-np /
  6. The P ≠ NP "Proof" Is One Week Old - rjlipton.wordpress.com/2010/08/15/the-p ≠ np-proof-is-one-week-old /
  7. Deolalikar P vs NP paper - michaelnielsen.org/polymath1/index.php? title = Deolalikar_P_vs_NP_paper (Англ.) . michaelnielsen.org. архіві - www.webcitation.org/61JL05sl0 з першоджерела 30 серпня 2011.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Теорія полів класів
Рівність
Асимптотичне рівність
Рівність третій
Рівність статей
Соціальна рівність
Рівність Парсеваля
Рівність (математика)
© Усі права захищені
написати до нас