Най-големият проблем в информатиката: P срещу NP

Съществуват седем математически проблема, обявени за толкова трудни и интересни, че Математическият институт „Клей“ ги е нарекъл проблеми на хилядолетието, а за решаването на всеки от тях този, който го реши, получава награда един милион долара. Един от проблемите засяга и информатиката и се нарича проблем P срещу NP. Нека обясним за какво всъщност става дума.

Ами така. Да не се залъгваме, че ще е лесно да се обясни. Все пак е проблем на хилядолетието. Затова иди да си направиш хубав зелен чай 🍵 и да започваме. Първо ще разгледаме четири различни задачи от света на информатиката и алгоритмите. Ще ги анализираме и ще видим каква е връзката им с буквите P и NP.

Задача № 1: Намиране на най-малкото число

P срещу NP засяга алгоритмите и тяхната сложност. Представи си, че изсипвам пред теб сто листчета, на всяко от които е написано по едно число, и искам да ми намериш листчето, на което е написано най-малкото число. Колко време ще ти отнеме?

Половин минута? Две минути?

Това са мерни единици за време, които в теоретичната информатика не ни интересуват чак толкова. Интересува ни повече броят на операциите. Можем да попитаме малко по-различно: колко листчета трябва да проверя, за да съм сигурен, че съм намерил най-малкото число? Отговорът е, че трябва да проверя всички листчета – защото най-малкото число може да е на последното листче. Ако ти хвърля сто листчета, трябва да провериш сто листчета. Ако ти хвърля хиляда, трябва да провериш хиляда. В общия случай, ако ти хвърля n листчета, трябва да провериш n листчета.

Това наричаме сложност на алгоритмите. Ако ти хвърля n листчета и трябва да извършиш n операции, за да намериш най-малкото число, това означава, че този алгоритъм за търсене на най-малкото число има сложност n, което наричаме още линейна сложност, защото сложността се описва от линейна функция.

Добре, прегледа сто листчета и съобщи, че най-малкото число е 17. Как мога да проверя, че казваш истината? Няма друг начин, освен отново да прегледам всички листчета и да проверя, че на нито едно няма по-малко число. Тоест ти трябва да погледнеш n листчета, за да намериш най-малкото число, а аз, когато искам да проверя, трябва да направя същото. Сложността на проверката на резултата също е n, линейна сложност.

Има ли алгоритми, при които е по-лесно да проверим резултата, отколкото да го намерим?

Задача № 2: Произведение на двойка

Представи си, че изсипвам пред теб две еднакво големи купчинки листчета, на всяко листче отново е написано по едно число. И сега искам да намериш число от купчинка A и число от купчинка B така, че произведението им да е числото 918. За пример нека имаме такива купчинки с числа:

$$\begin{array}{rcl}A& =& \{49;11;32;54;15\}\\ B& =& \{17;64;74;61;21\}\end{array}$$

По какъв начин можем да намерим двойка числа, чието произведение е равно на 918? Ами можем просто да изпробваме всички възможности. Колко са те? Доста, общо 25. Започваме, като умножим първото число от купчинка A, т.е. числото 49, с всяко число от купчинка B:

$$\begin{array}{rcl}49\cdot 17& =& 833\\ 49\cdot 64& =& 3136\\ 49\cdot 74& =& 3626\\ 49\cdot 61& =& 2989\\ 49\cdot 21& =& 1029\end{array}$$

Нито една двойка числа не дава 918. Затова опитваме същото с останалите числа от купчинка A, т.е. още пет двойки за числото 11, още пет двойки за числото 32, още пет двойки за 54 и последните пет двойки за 15. Общо можем да изпробваме 25 двойки числа. Накрая установяваме, че 54 · 17 = 918.

Каква е сложността на този алгоритъм? Интересува ни колко двойки числа трябваше да умножим. Двете купчинки съдържаха по пет листчета и ние трябваше да опитаме всяко от петте числа от първата купчинка с всяко от петте числа от втората купчинка. Общо опитахме 5 · 5 = 25 комбинации. Ако пред теб хвърля две купчинки по 10 листчета, ще трябва да опиташ 10 · 10 = 100 комбинации. Като обобщим, ако пред теб хвърля две купчинки по n листчета, трябва да изпробваш n · n = n² комбинации.

Казваме, че този наш алгоритъм има сложност n², квадратична сложност, защото тя се описва от квадратна функция.

Колко трудно обаче ще е да проверим резултата? Ако ми отговориш, че 54 и 17 са числата, чието произведение е 918, не ми се налага да преглеждам всички двойки числа от двете купчинки, както трябваше да направиш ти. Достатъчно е да умножа тази една двойка 54 · 17 и ще знам дали си прав, или не. Така че докато за решаването на задачата трябва да се пресметнат до n² произведения, за проверката стига да се пресметне само едно произведение. Проверката има константна сложност 1.

С това тази задача се различава осезаемо от предишната, където ни бяха нужни еднакво на брой стъпки за самото пресмятане и за последващата проверка.

Тази задача е и с порядък по-сложна от предишната. Ако изсипя пред теб десет хиляди листчета и искам да намериш най-малкото число, вероятно ще можеш да го намериш за един ден. Ако обаче изсипя пред теб два пъти по десет хиляди листчета и те накарам да търсиш произведението, ще трябва да провериш десет хиляди по десет хиляди произведения, което са сто милиона пресмятания. Дори да опитваш по едно произведение в секунда, ще ти отнеме около три години.

Задача № 3: Сума на подмножество

Нека разгледаме третата задача. Този път изсипвам пред теб дванадесет листчета с числа и искам да намериш произволен брой листчета, чийто сбор е нула. Например:

$$A=\{24;-69;1;-15;-76;-60;16;-83;48;-22;54;-47\}$$

Избери от тези числа произволна група числа, чийто сбор е 0. Например числата

$$24+48-69+1$$

дават сбор 4 и затова не са верният отговор. Верният отговор е групата числа… и знаеш ли какво? Опитай се да я намериш сам като домашно 😉. Има единствена група числа, чийто сбор е 0. Поне ще изпиташ колко е трудна тази задача.

Сега трябва да знаем сложността на тази задача. Самото пресмятане вече не е съвсем тривиално и е по-скоро за ценители. Така че ако те интересува как може да се пресметне сложността на тази задача, продължи да четеш. Иначе можеш да прескочиш към следващия раздел. ⏩

По какъв начин можем да намерим група числа, чийто сбор е 0? Ами просто трябва да изпробваме всички възможни комбинации от числа. Трябва да изпробваме всички двойки числа, всички тройки, четворки, петорки и т.н. и за всяка група да проверим дали сборът ѝ е нула. Колко такива комбинации има?

Нека го покажем с по-малко множество от числа. Колко различни групи числа, т.е. подмножества, мога да образувам от тройката числа B = {5; 7; 9}? Общо са осем:

$$\begin{array}{rcl}{B}_1& =& \left\{\right\}\\ B_2& =& \left\{5\right\}\\ B_3& =& \left\{7\right\}\\ B_4& =& \left\{9\right\}\\ B_5& =& \{5;9\}\\ B_6& =& \{5;7\}\\ B_7& =& \{7;9\}\\ B_8& =& \{5;7;9\}\end{array}$$

Забележи, че броим и празното подмножество B₁. Сега не е особено полезно, но за пълнота го оставихме. За да си улесним пресмятането, на всяко подмножество съпоставяме двоичен вектор. Двоичният вектор е просто редица от нули и единици, например 00101010. Ще работим с двоични вектори с дължина три. Вектор съпоставяме така: 101 съпоставяме на подмножеството, което съдържа „първото и третото число от първоначалното множество, но не и второто число“, т.е. на множеството {5; 9}. Вектор 110 съпоставяме на подмножеството, което съдържа „първото и второто число от първоначалното множество, но не и третото“, т.е. на множеството {5; 7} и т.н.

$$\begin{array}{rcl}{B}_1=\left\{\right\}& \to & 000\\ B_2=\left\{5\right\}& \to & 100\\ B_3=\left\{7\right\}& \to & 010\\ B_4=\left\{9\right\}& \to & 001\\ B_5=\{5;9\}& \to & 101\\ B_6=\{5;7\}& \to & 110\\ B_7=\{7;9\}& \to & 011\\ B_8=\{5;7;9\}& \to & 111\end{array}$$

Виждаме, че всяко подмножество има точно един двоичен вектор с дължина три. И всеки двоичен вектор с дължина три отговаря на точно едно подмножество. Тоест ако пресметнем колко различни двоични вектора с дължина n има, ще получим броя на различните комбинации, които можем да съставим, ако на входа имаме n различни числа. Нека го пресметнем.

Двоични вектори с дължина едно има два: 0 и 1.

Двоичните вектори с дължина две получаваме, като вземем всички двоични вектори с дължина едно и в края на всеки вектор добавим 0: получаваме векторите 00 и 10. Отново вземаме всички вектори с дължина 1 и в края добавяме 1: 01 и 11. Така получихме всички вектори с дължина 2: 00, 01, 10 и 11.

Двоичните вектори с дължина три получаваме, като вземем всички двоични вектори с дължина две и в края добавим нула: 000, 010, 100 и 110, и единица: 001, 011, 101 и 111.

И така нататък за всяка следваща дължина. Виждаме, че когато увеличим дължината на двоичния вектор с едно, броят на различните двоични вектори нараства два пъти. За дължина на вектора четири бихме получили общо 2 · 2 · 2 · 2, което е 16, различни комбинации.

В общия случай можем да изведем, че ако имаме множество M с n елемента, то броят на всички подмножества на това множество M е равен на броя на всички различни двоични вектори с дължина n и това е равно на

$$\underset{n\text{ пъти}}{\underbrace{2\cdot 2\cdot \dots \cdot 2}}=2^n$$

2ⁿ или n² – не е ли все едно? Все тая 🤷‍♂

Съществуват 2ⁿ различни подмножества, които можем да образуваме от множество с n числа. В нашия случай имаме n = 12 числа и значи трябва да проверим 2¹² различни комбинации, което са 4096 комбинации. Казваме, че тази задача има сложност 2ⁿ, експоненциална сложност, защото я описва показателна функция.

Забележи, че предишната задача имаше сложност n², докато тази има сложност 2ⁿ. Изглежда много сходно, нали? Само че има голяма разлика между това да имаме постоянен степенен показател и да имаме там променливата n. Забележи, че когато n = 4, получаваме

$$\begin{array}{rclrc}{n}^2& =& 4^2& =& 16\\ 2^n& =& 2^4& =& 16\end{array}$$

Добре, засега излиза същото. А ако n = 10?

$$\begin{array}{rclrc}{n}^2& =& {10}^2& =& 100\\ 2^n& =& 2^{10}& =& 1024\end{array}$$

Ого, показателната функция скочи и изведнъж е около десет пъти по-голяма от квадратната. Какво получаваме за n = 20?

$$\begin{array}{rclrc}{n}^2& =& {20}^2& =& 400\\ 2^n& =& 2^{20}& =& 1048576\end{array}$$

Експоненциалната сложност за n = 20 има около 2600 пъти по-висока стойност от квадратната сложност. Виждаме, че показателната функция расте много по-бързо от квадратната функция. Спомни си това, когато ни връхлети поредната пандемия, която се разпространява сред населението с експоненциална скорост.

Ако пред теб хвърля двадесет листчета, ще трябва да провериш 1 048 576 комбинации. Това е доста.

Как проверяваме верността на резултата?

Колко време ще ми отнеме да проверя, че получената група числа наистина дава сбор 0? Това ще стане сравнително бързо – просто събирам тази една група числа и ако сборът ѝ е равен на 0, значи си намерил правилната група листчета, а ако сборът е друг, значи си намерил грешен набор от листчета.

Отново виждаме, че проверката на резултата е с порядък по-лесна от намирането му.

Задача № 4: Задачата за търговския пътник

Задачата за търговския пътник е една от най-известните алгоритмични задачи. Грубо казано, имаме търговски пътник, който продава дъжд. И този търговски пътник трябва много да пътува, за да изкара прехраната си. Затова решава да посети всеки от 14-те най-големи града в България. И тъй като не иска да си пилее времето, решава да намери най-краткия възможен маршрут, който го води през всички тези градове. А нашата задача е да намерим такъв най-кратък маршрут.

Как можем да намерим този най-кратък маршрут? Изпробваме всички възможности.

Можем да си го опростим. Да си представим, че между всеки два града има точно един най-къс път. По какъв начин можем да намерим най-краткия маршрут през всички градове? Градовете са 14. Значи имаме 14 възможности откъде да започнем. Да речем, че сме започнали във Варна!!! Къде можем да стигнем от Варна? На теория можем да отидем във всеки друг град. Значи можем да избираме измежду 13-те останали града.

Вече можем да пресметнем, че имаме общо 14 · 13 възможности да посетим първите два града – имаме 14 възможности откъде да започнем и после можем да избираме от 13-те останали града.

Когато стигнем във втория град, трябва да продължим нататък. В два града вече сме били, така че можем да отпътуваме към един от 12-те останали града. Така имаме общо 14 · 13 · 12 възможности да посетим първите три града.

След като посетим третия град, трябва да изберем един от 11-те останали града, после един от 10-те останали града и т.н.

След като посетим всички, установяваме, че сме имали да избираме общо от

$$14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$$

възможности. Това може да ти напомня за факториел, който означаваме с удивителен знак. Така можем да кажем, че това произведение е равно на 14!:

$$14!=14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$$

и следователно съществуват 14! маршрута, които минават през всички тези градове. Много ли е? Доста, защото

$$14!=87178291200.$$

В общия случай, ако търсим най-краткия маршрут между n града, ще трябва да опитаме n! различни маршрута. Сложността на това решение е n!.

Как бихме проверили, че сме намерили правилния резултат? Ако ми кажеш, че най-краткият маршрут е от Бургас до Варна, после до Пловдив и т.н., как мога да проверя, че казваш истината? Ами трудно 🤷‍♂. Защото когато погледна този маршрут, нямам лесен начин да проверя дали именно той е най-кратък. Всъщност трябва да извърша цялото пресмятане отново. Сложността на проверката на резултата също е n!.

Класовете P и NP

Разгледахме четири задачи и алгоритмите, които ги решават, и анализирахме колко е трудно да се намери решението и колко е трудно да се провери то. Можем да обобщим това в следната таблица:

Сега ще разделим нашите задачи на две групи. Първата група ще съставят задачите, които са лесни за решаване. Това са задачите, които могат да се решат със сложност n или n² или n³ или n⁴ и т.н. Тъй като изрази като n² наричаме полиноми, този клас задачи означаваме с буквата P. Казваме, че класът P съдържа задачите, които могат да се решат за полиномиално време (= имат сложност например n² или n⁷). Най-общо казано, това са задачи, които могат да се решат сравнително лесно.

Към класа P принадлежи задача № 1, намирането на най-малкото число, защото има сложност на решаването n, и задача № 2, произведението на двойка, защото сложността на решаването ѝ е n², а и двете са полиноми.

Вторият клас е класът NP. Той съдържа задачите, които могат да се проверят за полиномиално време. Към класа NP така принадлежат всички задачи освен последната. Задачата за търговския пътник не можем да проверим за полиномиално време. Предишните три задачи могат да се проверят за полиномиално време.

Задачата за търговския пътник не можем нито да решим, нито да проверим за полиномиално време. За нея ни е нужен още един клас, който да съдържа още по-трудни задачи. Този клас съществува, но за нас сега не е интересен.

Ясно е, че класът P е подмножество на класа NP. Тоест всяка задача от класа P е едновременно и в класа NP. Има смисъл – ако можем да решим дадена задача за полиномиално време, можем и да проверим резултата за полиномиално време.

Проблемът P срещу NP

А вярно ли е и обратното? Всяка ли задача от класа NP е едновременно и в класа P? Тоест ако има начин да се провери резултатът на задачата за полиномиално време, има ли и алгоритъм, който би решавал тази задача за полиномиално време?

Например знаем, че можем да проверим резултата на задача № 3, сумата на подмножество, за полиномиално време. Но за решаването ѝ използвахме алгоритъм, който не е полиномиален – използваният алгоритъм има експоненциална сложност 2ⁿ. Знаем ли обаче със сигурност, че за тази задача не съществува никакъв алгоритъм с полиномиална сложност?

Не знаем!

Съвсем възможно е за всяка задача, която може да се провери за полиномиално време, да съществува алгоритъм, който я решава за полиномиално време. Ние не го знаем. Не можем да докажем съществуването на такъв алгоритъм, но не можем и да опровергаем съществуването му.

Ако за всяка задача от класа NP съществуваше алгоритъм, който я решава за полиномиално време, това би означавало, че класът NP е равен на класа P. Всички задачи от класа P биха били в класа NP и всички задачи от класа NP биха били в класа P – двата класа биха били равни, биха съвпадали.

Проблемът P срещу NP е въпросът дали класът P съвпада с класа NP, или това са два различни класа задачи.

Или е изпълнено P = NP, или е изпълнено P ≠ NP. Това никой не знае и ако го откриеш, те чака награда един милион долара, вечна слава и вероятно също наградата „Тюринг“, която е нещо като Нобеловата награда за информатиците.

Какво би станало, ако P = NP?

Какво би станало, ако е изпълнено P = NP? Не е съвсем лесно да се каже какво би станало. Щяхме да знаем, че за всички задачи от класа NP съществува алгоритъм, който ги решава за полиномиално време. Например че за нашата задача № 3, сумата на подмножество, съществува алгоритъм, който я решава за полиномиално време. Само че има три подводни камъка:

• Това, че бихме знаели, че такъв алгоритъм съществува, не означава, че можем да го намерим. Просто щяхме да знаем, че да, съществува алгоритъм, който решава задачата за полиномиално време, но може би още сто години нямаше да можем да го построим. Това е нещо подобно на случая, когато общата теория на относителността предсказа съществуването на черни дупки, но въпреки това ни трябваха още няколко десетилетия, докато успеем да направим първата „снимка“ на черна дупка.
• Това, че съществува алгоритъм, работещ за полиномиално време, за съжаление още не означава, че е бърз. Бихме могли да намерим алгоритъм със сложност n¹⁰⁰. Изразът n¹⁰⁰ също е полином. Когато сравним сложностите 2ⁿ и n¹⁰⁰, установяваме, че докато n е сравнително малко, алгоритъмът със сложност 2ⁿ все още се нуждае от по-малко операции. Например за n = 20 имаме 2²⁰ = 1 048 576, докато изразът 20¹⁰⁰ води до число, което има около 130 цифри, т.е. е с около 120 порядъка по-голямо от 1 048 576. Нашият полиномиален алгоритъм би бил в действителност по-бавен от експоненциалния. Поне докато n е сравнително малко.
• Ако все пак успеехме да намерим бърз алгоритъм, работещ за полиномиално време, бихме могли да решаваме много задачи по-бързо и с по-голяма точност. Това, разбира се, е положителна новина, но има и своите негативи. Съществува област, която разчита на това, че някои задачи се решават трудно, и това е криптографията – шифроването. Би могло да стане с порядък по-лесно да се разбиват сегашните шифри.

Интермецо: тъй като стигна дотук, като награда ще ти издам, че решението на задача № 3 е 24 + 1 − 60 + 16 − 83 + 48 + 54.

Какво би станало, ако P ≠ NP?

Ако класовете задачи P и NP са различни, не би станало кой знае какво, защото това повече или по-малко е статуквото. Към момента нямаме алгоритъм, който да решава някоя трудна задача от NP за полиномиално време, и ако някой докаже, че P ≠ NP, това просто би си останало така завинаги. Далеч по-голяма сензация би била доказателство, че P = NP.

Препратки в попкултурата

• В един епизод на „Семейство Симпсън“ виждаме как Хоумър попада в нещо като алтернативна реалност, в която му се разкрива, че P = NP. Може да се види на youtube.com.
• Във „Футурама“ пък виждаме, че имат в склада две папки, едната с надпис P и другата с надпис NP. Може да се види на youtube.com.
• Вторият епизод от втория сезон на сериала Елементарно (на английски „Elementary“) със заглавие „Solve for X“ е посветен на убийство на математик, който вероятно е решил проблема P срещу NP.