Наконец-то! P?=NP и институт Клэя

[Organon]

В конце прошлой записи мы вплотную подошли к проблеме равенства классов сложности P и NP. Сформулировать ее можно следующим образом:

Если правильность ответа на какой-либо вопрос можно проверить за полиномиальное время, то верно ли, что этот ответ возможно так же быстро найти (т.е. за полиномиальное время и используя полиномиальную память)?

Проблема Кука (P=?NP) ждет своего разрешения уже 37 лет. Интуитивно, вроде бы ясно, что эти классы ну никак не могут быть равны. И сейчас (поскольку никто не может доказать их равенство) все ведут себя так, как будто они и неравны.
Из определения классов Р и NP (напомню, класс Р состоит из задач, разрешимых за полиномиальное время; класс NP состоит из задач, которые разрешимы с подсказкой за это же полиномиальное время) следует, что P ⊂ NP.

Т.е. если мы представим это в виде картинки, получим следующее:

P ⊂ NP

Однако до сих пор никто не может ни доказать, ни опровергнуть строгость этого включения, иными словами, найти такой алгоритм, который лежит в классе NP, но не принадлежит в P (т.е. находится в желтой части картинки).

Давайте посмотрим на NP-полные задачи.
Из определений классов следует, что класс Р — класс самых легких задач из NP. Класс NP-полных задач — самый сложный. NP-полные задачи решаются за экспоненциальное время, а это может быть очень, очень долго!


NPC ⊂ NP (где NPC — NP-Complete — NP-полные задачи)
На картинке классы Р и NPC не пересекаются:
NPC ∩ P = ∅

А что бы было, если бы они пересеклись? По определению NP-полной задачи к ней можно свести любую задачу из класса NP. Поэтому если хотя бы для одной из них удастся найти алгоритм решения за полиномиальное время — это будет означать: УРА! Проблема решена!

"Ура", да не очень "ура"!
Потому что если человечество научится быстро (за полиномиальное время) решать NP-полные задачи, последствия будут очень и очень печальными.
Практическая криптография (по большей части) окажется бесполезной. Вся защищенная информация окажется полностью "беззащитной". Заходи, кто хочешь, бери, что хочешь!
Кроме этого, теория алгоритмической сложности испытает очень существенные потрясения. Потому что есть еще много-много разных классов, о которых я здесь просто не упоминала, но часть из них образует (бесконечную) иерархию внутри NP. Если же равенство P=NP будет доказано, вся эта иерархия свернется в один единственный класс Р.

Однако же, я думаю, выгоды тоже будут колоссальными! Мы научимся считать быстро! Всё!

А вот повторю то, о чем писала в прошлый раз:
Проблема равенства классов P и NP является одной из семи проблем, за решение которых Математический институт Клэя назначил премию в 1 млн. долларов США.

Кстати, на сайте этого института дано уморительное описание этой проблемы!
www.claymath.org/millennium/P_vs_NP/
Не поленюсь даже и переведу. (Хотя за точность перевода ручаться не буду)
***
Предположим, вы организуете расселение четырехсот студентов университета. Однако (как всегда) общежитие не может вместить всех, и места в этом общежитии получат только сто из них. Чтобы усложнить вашу задачу, декан выдал вам список пар "несовместимых студентов" и потребовал, чтобы ни одна пара из этого списка не оказалась вместе!
Это пример того, что ученые называют NP-задачей, т.к. легко проверить, является ли определенный выбор ста студентов подходящим (т.е. ни одна пара из результирующего списка не оказалась в списке, выданном деканом), однако задача формирования такого списка с нуля кажется настолько трудной, что выполнить ее практически невозможно.
В самом деле, общее число путей выбора ста студентов из четырехсот кандидатов больше чем число атомов в нашей Вселенной! (прим. АР: неужели правда? С₄₀₀¹⁰⁰ — больше, чем число атомов Вселенной? Хотя что это я... Если всего-то до миллиарда можно считать больше 30 лет...)
Таким образом никакая цивилизация будущего не может даже надеяться на создание суперкомпьютера, способного решить эту задачу с помощью "грубой силы" )))), т.е. проверяя каждую возможную комбинацию 100 студентов из 400. Однако эта очевидная трудность может всего лишь отражать недостаток изобретательности вашего программиста ))))
Фактически, это одна из выдающихся проблем информатики — доказать существование или несуществование такого вопроса, ответ на который можно легко проверить, но который требует невероятно долгого времени для своего решения любым прямым методом.
Задачи, аналогичные той, которую мы рассмотрели, точно кажутся именно такими! Но однако до сих пор никто не смог доказать, что хотя бы одна из них, на самом деле настолько сложна, как кажется! Т.е. что на самом деле нет ни одного возможного способа получить ответ с помощью компьютера. Стивен Кук и Леонид Левин сформулировали проблему Р (т.е. легко найти) vs NP (т.е. легко проверить) независимо друг от друга в 1971 г.
(Конец цитаты)

Так что если кто-то таки найдет доказательство равенства этих классов, смело сможет расселять студентов по общежитиям)))
А на самом деле, всё-таки, надо полагать, кроме огромного минуса в виде полного кризиса в области защиты данных, человечество получит и грандиозный плюс! Решать быстро задачи такого класса сложности — оооо, этим надо гордиться! Только вот что-то расправляться с этой проблемой никто не торопится...