P срещу NP: Най-голямото предизвикателство в информатиката и неговото значение
Проблемът \(P\) срещу \(NP\) —
най-важният нерешен въпрос в информатиката
Награда от един милион долара, фундаментални последици за алгоритмите, оптимизацията и криптографията — всичко това е свързано с един на пръв поглед прост въпрос: ако можем бързо да проверим дадено решение, можем ли също толкова бързо да го намерим?
Проблемът \(P\) срещу \(NP\) е смятан за едно от най-важните нерешени предизвикателства в теоретичната информатика и математиката. Той е включен сред седемте проблема на хилядолетието на Института „Клей“, а за решението му е определена награда от 1 000 000 долара. Значението му обаче далеч надхвърля размера на наградата: отговорът би променил разбирането ни за алгоритмите, оптимизацията, автоматичното доказване на теореми и т.нар. сложностно базирана криптография — тази, чиято сигурност почива на предположения за изчислителна трудност.
Какво означават \(P\) и \(NP\)?
Двата класа се различават по това колко трудно е да се стигне до верен отговор спрямо това колко лесно е да се провери вече даден отговор.
Задачи за вземане на решение (с отговор „да“ или „не“), които могат да бъдат решени от детерминистичен алгоритъм за полиномиално време спрямо размера на входа.
Задачи за вземане на решение, при които всеки вход с отговор „да“ има сертификат с полиномиална дължина, чиято коректност се проверява от детерминистичен алгоритъм за полиномиално време.
Очевидно е, че \(P \subseteq NP\): ако можем да решим дадена задача бързо, можем и да проверим предложен отговор бързо. Големият въпрос е дали включването е строго — тоест \(P \stackrel{?}{=} NP\). И едно уточнение: буквите \(NP\) не означават „неполиномиално“, а nondeterministic polynomial — недетерминистично полиномиално време.
„Полиномиално време“ означава, че броят на необходимите стъпки е ограничен от израз от вида \(T(n)=O(n^k)\), където \(n\) е размерът на входа, а \(k\) — фиксирана константа (например \(n^2\), \(n^5\) и т.н.). Това е удобен математически модел на „ефективно“ изчисление, но не буквално: алгоритъм с време \(n^{100}\) е полиномиален, ала практически неизползваем. Обратно — функции като \(2^{\sqrt{n}}\) и \(n^{\log n}\) растат по-бавно от \(2^n\), но пак не са полиномиални и не спадат към \(P\).
Задачата за пътуващия търговец
Класически пример е решаващата версия на задачата за пътуващия търговец: дадени са \(n\) града, разстоянията между тях и число \(B\); пита се дали съществува маршрут, който посещава всеки град точно веднъж, връща се в началния град и има обща дължина не по-голяма от \(B\). При симетричния вариант (с фиксиран начален град и без разлика в посоката на обхождане) броят на маршрутите е \(\frac{(n-1)!}{2}\) — за 100 града това са приблизително \(4{,}67\cdot 10^{155}\). Прякото им изчерпване е практически невъзможно: дори по един маршрут на наносекунда от Големия взрив насам, не бихте се доближили до края.
Въпреки многото умни евристични методи, никой досега не е открил алгоритъм, който решава тази задача за полиномиално време. Но ако ви подадат конкретен маршрут, проверката е бърза: трябва само да се провери, че всеки град е посетен точно веднъж, че маршрутът се затваря и че общата му дължина не надхвърля \(B\). Именно тази асиметрия между намирането и проверката е същността на \(NP\).
Недетерминистично изчисление
Буквата „N“ в \(NP\) означава „недетерминистично“. Формалната дефиниция на класа \(NP\) — тази, с която работят теоретиците — не говори за „проверка“, а за изчисление: \(NP\) е множеството от задачи, решими за полиномиално време от недетерминистична машина на Тюринг. Доказано е, че двете дефиниции — чрез проверка и чрез недетерминистична машина — са математически еквивалентни.
Какво е машина на Тюринг?
Машината на Тюринг е теоретичен модел на изчисление, въведен от Алън Тюринг през 1936 г. в статията „On Computable Numbers, with an Application to the Entscheidungsproblem“. Тя се състои от неограничена лента, разделена на клетки, глава за четене и запис и краен набор от състояния и правила за преход. Въпреки простото си устройство, машината може да симулира всеки обикновен алгоритъм; твърдението, че всяка ефективно изчислима функция е изчислима и от машина на Тюринг, е известно като тезата на Чърч–Тюринг.
Недетерминистичната машина на Тюринг е формален модел, при който от една конфигурация са разрешени няколко различни следващи прехода. Затова нейното изчисление не е една-единствена последователност, а разклоняващо се дърво от възможни пътища. Машината приема входа, ако поне един път достига приемащо състояние в рамките на полиномиален брой стъпки. Това не описва реален компютър, който изпълнява всички възможности едновременно — то е абстрактна математическа конструкция.
История: как се ражда проблемът?
През 1959 г. Майкъл Рабин и Дейна Скот публикуват статията „Крайни автомати и техните задачи за разрешимост“, в която систематично въвеждат и изследват недетерминистичните крайни автомати и доказват, че по разпознавателна мощност те са равностойни на детерминистичните. С тази работа недетерминизмът се превръща в основен инструмент на теорията на автоматите. (Недетерминистичният автомат приема дадена входна дума, ако поне една от възможните последователности от избори води до приемащо състояние.)
Съвременната теория започва през 1971 г. със статията на Стивън Кук „Сложността на процедурите за доказване на теореми“. Кук въвежда понятието \(NP\)-пълнота и доказва, че задачата за удовлетворяемост на булеви формули (SAT) е пълна за класа \(NP\).
Независимо от него, от другата страна на Желязната завеса, Леонид Левин развива сходна теория на универсалните задачи за търсене; резултатите му са публикувани през 1973 г. Заради независимия принос на двамата основополагащата теорема — че SAT е пълна за \(NP\) — днес носи името теорема на Кук–Левин.
През 1972 г. Ричард Карп показва как резултатът на Кук може да се използва за доказване на \(NP\)-пълнотата на още 20 естествени комбинаторни задачи; заедно с изходната SAT те образуват прочутия списък на 21-те задачи на Карп. Сред тях са задачата за клика (CLIQUE), покритието с върхове, Хамилтоновият цикъл и сумата на подмножества. Днес са известни хиляди \(NP\)-пълни задачи.
Две еквивалентни лица на \(NP\)
Класът \(NP\) може да бъде описан по два еквивалентни начина. От гледна точка на проверката той съдържа задачите, чиито положителни отговори имат полиномиално дълги сертификати, проверими за полиномиално време. От гледна точка на изчислителните модели той съдържа задачите, решими за полиномиално време от недетерминистична машина на Тюринг.
Двете описания съвпадат по естествен начин: недетерминистичната машина може да „познае“ сертификат и след това да го провери, а обратно — всеки приемащ път на такава машина може да се запише като сертификат и да се провери детерминистично. При детерминистичната машина следващата конфигурация е еднозначно определена; при недетерминистичната еднозначното правило за преход се заменя с отношение, допускащо няколко възможни прехода. Тази малка формална промяна не увеличава множеството на изчислимите задачи, но може да промени времевата им сложност — и точно дали тази привидна разлика в ефективността е реална, стои в сърцето на \(P\) срещу \(NP\).
Проблемът \(P\) срещу \(NP\) стои нерешен вече повече от половин век. Широко разпространеното очакване е, че \(P \neq NP\), но до днес няма доказателство нито за равенството, нито за неравенството. Въпросът има и по-широко звучене: в много ситуации е лесно да разпознаем правилното решение, щом го видим, но изключително трудно да го открием сами. \(P\) срещу \(NP\) пита дали тази разлика може да се превърне в строга математическа граница, или е само отражение на това, че още не сме намерили достатъчно добри алгоритми.
Запишете урок
Индивидуални и групови онлайн уроци по математика за цялата страна
- ›НВО по математика след 7. клас
- ›НВО по математика след 10. клас
- ›Кандидатстудентски изпити по математика
- ›Подготовка по математика за ISEE, SAT и A Level
- ›Усвояване на текущия учебен материал (всички класове)
- ›Студенти: математически анализ, линейна алгебра, аналитична геометрия, диференциални уравнения, теория на вероятностите, статистика и др.
Харесва ли ви съдържанието?
Ако тази статия ви е харесала, можете да подкрепите създаването на нови безплатни материали.
Коментари
Публикуване на коментар