P проти NP: найбільша загадка інформатики

Існує сім математичних задач, які визнали такими складними й цікавими, що Математичний інститут Клея назвав їх задачами тисячоліття, а той, хто розв'яже будь-яку з них, отримає мільйон доларів. Одна з цих задач стосується й інформатики, і називається проблемою P проти NP. Давай розберемося, про що вона насправді.

Одразу попереджаю: легко не буде. Усе-таки це задача тисячоліття. Тож іди завари собі гарного зеленого чаю 🍵 і починаємо. Спершу розглянемо чотири різні задачі зі світу інформатики й алгоритмів. Проаналізуємо їх і побачимо, як вони пов'язані з літерами P і NP.

Задача № 1: знайти найменше число

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

Пів хвилини? Дві хвилини?

Такі одиниці часу в теоретичній інформатиці нас не надто цікавлять. Нас цікавить радше кількість операцій. Тож спитаймо інакше: скільки папірців треба перевірити, щоб бути певним, що знайдено найменше число? Відповідь: треба перевірити всі папірці — адже найменше число може лежати на останньому. Коли я кидаю перед тобою сто папірців, ти перевіряєш сто папірців. Коли тисячу — тисячу. Загалом, коли перед тобою n папірців, треба перевірити n папірців.

Це й називають складністю алгоритмів. Якщо перед тобою n папірців і щоб знайти найменше число, треба виконати n операцій, то алгоритм пошуку найменшого числа має складність n. Таку складність ще називають лінійною, бо її описує лінійна функція.

Гаразд, сто папірців перебрано, і ти повідомляєш, що найменше число — 17. Як мені перевірити, що це правда? Іншого шляху, ніж знову пройти всі папірці й пересвідчитися, що меншого числа немає, не існує. Тобто ти мусиш подивитися на n папірців, щоб знайти найменше число, а я, щоб це перевірити, мушу зробити те саме. Отже, складність перевірки результату теж дорівнює n — лінійна складність.

А чи бувають алгоритми, де перевірити результат простіше, ніж його знайти?

Задача № 2: добуток пари

Уяви, що я висипаю перед тобою дві купки папірців однакового розміру, на кожному папірці знову одне число. Тепер я прошу знайти число з купки A і число з купки B, добуток яких дорівнює 918. Наприклад, нехай купки такі:

$$\begin{eqnarray} A &=& \left\{49, 11, 32, 54, 15\right\}\\ B &=&\left\{17, 64, 74, 61, 21\right\} \end{eqnarray}$$

Як знайти пару чисел, добуток яких дорівнює 918? Та просто спробувати всі варіанти. Скільки їх буде? Чимало — 25. Почнемо з того, що помножимо перше число з купки A, тобто 49, на кожне число з купки B:

$$\begin{eqnarray} 49\cdot17&=&833\\ 49\cdot64&=&3136\\ 49\cdot74&=&3626\\ 49\cdot61&=&2989\\ 49\cdot21&=&1029\\ \end{eqnarray}$$

Жодна пара не дає 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 = \left\{24,-69{,}1,-15,-76,-60{,}16,-83{,}48,-22{,}54,-47\right\} $$

Вибери з цих чисел будь-яку групу, сума яких дорівнює 0. Наприклад, числа

$$24+48-69+1$$

дають суму 4, тож це не правильна відповідь. Правильна відповідь — це група чисел… А знаєш що? Спробуй знайти її власноруч як домашнє завдання 😉. Така група єдина. Принаймні відчуєш, наскільки ця задача важка.

Тепер нам потрібно знати складність цієї задачі. Саме обчислення вже не зовсім тривіальне й більше для гурманів. Тож якщо цікаво, як обчислити складність цієї задачі, читай далі. А якщо ні, можеш перескочити до наступного розділу. ⏩

Отже, як знайти групу чисел із нульовою сумою? Та просто перебрати всі можливі комбінації чисел. Треба спробувати всі пари, всі трійки, четвірки, п'ятірки тощо і для кожної групи перевірити, чи дорівнює її сума нулю. Скільки існує таких комбінацій?

Покажімо це на меншій множині чисел. Скільки різних груп чисел, тобто підмножин, можна утворити з трьох чисел B = {5, 7, 9}? Усього їх вісім:

$$\begin{eqnarray} B_1&=&\left\{\right\}\\ B_2&=&\left\{5\right\}\\ B_3&=&\left\{7\right\}\\ B_4&=&\left\{9\right\}\\ B_5&=&\left\{5{,}9\right\}\\ B_6&=&\left\{5{,}7\right\}\\ B_7&=&\left\{7, 9\right\}\\ B_8&=&\left\{5{,}7,9\right\}\\ \end{eqnarray}$$

Зверни увагу, що ми врахували й порожню підмножину B₁. Зараз від неї мало користі, але для порядку ми її залишили. Щоб спростити обчислення, поставимо кожній підмножині у відповідність двійковий вектор. Двійковий вектор — це просто послідовність нулів і одиниць, наприклад 00101010. Ми працюватимемо з двійковими векторами довжини три. Вектор 101 відповідає підмножині, що містить «перше й третє число вихідної множини, але не друге», тобто множині {5, 9}. Вектор 110 відповідає підмножині, що містить «перше й друге число вихідної множини, але не третє», тобто множині {5, 7} і так далі.

$$\begin{eqnarray} B_1=\left\{\right\}&\rightarrow&000\\ B_2=\left\{5\right\}&\rightarrow&100\\ B_3=\left\{7\right\}&\rightarrow&010\\ B_4=\left\{9\right\}&\rightarrow&001\\ B_5=\left\{5{,}9\right\}&\rightarrow&101\\ B_6=\left\{5{,}7\right\}&\rightarrow&110\\ B_7=\left\{7, 9\right\}&\rightarrow&011\\ B_8=\left\{5{,}7,9\right\}&\rightarrow&111\\ \end{eqnarray}$$

Бачимо, що кожна підмножина має рівно один двійковий вектор довжини три. І кожен двійковий вектор довжини три відповідає рівно одній підмножині. Отже, якщо ми обчислимо, скільки існує різних двійкових векторів довжини 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, а вона дорівнює

$$\underbrace{2\cdot2\cdot\ldots\cdot2}_{n\text{ разів}}=2^n$$

2ⁿ чи n² — хіба не однаково? 🤷‍♂

Отже, з множини з n чисел можна утворити 2ⁿ різних підмножин. У нашому випадку n = 12 чисел, тож треба перевірити 2¹² різних комбінацій, а це 4096 комбінацій. Кажуть, що ця задача має складність 2ⁿ, експоненційну складність, бо її описує показникова функція.

Зверни увагу: попередня задача мала складність n², а ця — 2ⁿ. Виглядає дуже схоже, правда? Але між тим, коли показник степеня сталий, і тим, коли в ньому стоїть змінна n, величезна різниця. Подивись: для n = 4 маємо

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

Гаразд, поки що виходить однаково. А що буде для n = 10?

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

Ого, показникова функція стрибнула й раптом стала приблизно вдесятеро більшою за квадратичну. А що вийде для n = 20?

$$\begin{eqnarray} n^2&=&20^2&=&400\\ 2^n&=&2^{20}&=&1~048~576 \end{eqnarray}$$

Експоненційна складність для n = 20 має значення приблизно в 2600 разів більше, ніж квадратична. Бачимо, що показникова функція зростає набагато швидше за квадратичну функцію. Згадай про це, коли нас знову накриє якась пандемія, що поширюватиметься серед населення експоненційно.

Якщо ж я кину перед тобою двадцять папірців, тобі доведеться перевірити 1 048 576 комбінацій. Це чимало.

Як перевірити правильність результату?

Скільки часу мені знадобиться, щоб перевірити, що знайдена група чисел справді дає суму 0? Це буде досить швидко: я просто додам цю одну групу чисел, і якщо сума дорівнює 0, то це правильна група папірців, а якщо сума інша — не та.

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

Задача № 4: задача комівояжера

Задача комівояжера — одна з найвідоміших алгоритмічних задач. Грубо кажучи, є комівояжер, який продає дощ. І йому доводиться багато їздити, щоб заробити на життя. Тому він вирішив відвідати 14 великих міст України. А що марнотратства він не любить, то вирішив знайти найкоротший можливий маршрут, який проведе його через усі ці міста. Наше завдання — такий найкоротший маршрут знайти.

Як його знайти? Спробуємо всі варіанти.

Можна трохи спростити. Уявімо, що між кожними двома містами існує рівно одна найкоротша дорога. Як знайти найкоротший маршрут через усі міста? Міст у нас 14. Тож є 14 варіантів, де почати. Припустімо, що ми почали в Харкові!!! Куди можна потрапити з Харкова? Теоретично — у будь-яке інше з міст. Тобто вибирати можна з 13 міст, що лишилися.

Уже зараз можна порахувати, що існує 14 · 13 варіантів відвідати перші два міста: 14 варіантів, де почати, а потім вибір із 13 міст, що лишилися.

Коли ми приїдемо до другого міста, треба їхати далі. У двох містах ми вже побували, тож можемо вирушити в одне з 12 міст, що лишилися. Отже, усього є 14 · 13 · 12 варіантів відвідати перші три міста.

Коли ми відвідаємо третє місто, треба вибрати одне з 11 міст, що лишилися, потім одне з 10 і так далі.

Коли ми відвідаємо всі міста, з'ясується, що вибирати довелося з

$$14\cdot13\cdot12\cdot11\cdot10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1$$

варіантів. Це може нагадувати факторіал, який позначають знаком оклику. Тож можемо сказати, що цей добуток дорівнює 14!:

$$14!=14\cdot13\cdot12\cdot11\cdot10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1$$

а отже, існує 14! маршрутів, що проходять через усі ці міста. Багато це чи ні? Таки багато, адже

$$14!=87~178~291~200.$$

Загалом, якби ми шукали найкоротший маршрут між 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.
• Друга серія другого сезону серіалу «Елементарно» під назвою «Рішення для Х» присвячена вбивству математика, який, імовірно, розв'язав проблему P проти NP.