P срещу NP: Най-голямото предизвикателство в информатиката и неговото значение
Проблемът \(P\) срещу \(NP\) —
най-важният нерешен въпрос в информатиката
Милион долара награда, разклатена интернет сигурност, революция в изчислителните науки — всичко това зависи от отговора на един въпрос: дали намирането на решение е по-трудно от проверката му?
Проблемът \(P\) срещу \(NP\) е смятан за най-голямото нерешено предизвикателство едновременно в информатиката и в математиката. Той е включен в списъка на седемте проблема на хилядолетието на Института Клей и носи награда от 1 000 000 долара. Но значението му надхвърля далеч всяка парична стойност: предположението \(P \neq NP\) е в основата на почти цялата съвременна интернет сигурност — от криптирането на банкови карти до блокчейн технологиите. Ако някой докаже, че \(P = NP\), тези системи биха се сринали.
Какво означават \(P\) и \(NP\)?
Двата класа се различават по това колко трудно е да се стигне до верен отговор спрямо това колко лесно е да се провери вече даден отговор.
Задачи, които могат да бъдат решени за полиномиално време. С нарастването на входните данни времето за решаване расте умерено — като степенна функция на размера им.
Задачи, чиито решения могат да бъдат проверени за полиномиално време. Намирането на решение може да е трудно; проверката му — бърза.
„Полиномиално" означава, че времето за изчисление може да се опише с полином — израз от вида \(f(n) = 4n^5 + 7n^3 - n + 1{,}5\), където \(n\) е размерът на входа. Всичко, което расте по-бавно от експоненциална функция, се счита за „ефективно" в теорията на изчислителната сложност.
Задачата за пътуващия търговец
Класически пример за задача в \(NP\) е задачата за пътуващия търговец: дадени са \(n\) града, търсим маршрут, минаващ през всички тях, с обща дължина под зададена граница. Броят на възможните маршрути е \(\frac{(n-1)!}{2}\) — за 100 града това е около \(10^{155}\) варианта за проверка. Дори ако разгледате по един маршрут всяка наносекунда от Големия взрив насам, не бихте успели да ги изчерпите.
Въпреки многото умни евристични методи, досега никой не е открил алгоритъм, решаващ тази задача за полиномиално време. Но ако ви предоставят конкретен маршрут, проверката е тривиална — просто се сумират разстоянията между 100 града и се дава отговор „да" или „не". Точно тази асиметрия между намирането и проверката е същността на \(NP\).
Недетерминистично изчисление
Буквата „N" в \(NP\) означава „недетерминистично". Формалната дефиниция на класа \(NP\) — тази, с която работят теоретиците — не говори за „проверка", а за изчисление: \(NP\) е множеството от задачи, решими за полиномиално време от недетерминистична машина на Тюринг. Доказано е, че двете дефиниции — чрез проверка и чрез недетерминистична машина — са математически еквивалентни.
Какво е машина на Тюринг?
Машината на Тюринг е теоретичен модел на компютър, въведен от Алън Тюринг през 1936 г. Тя се състои от безкрайна лента с клетки, глава за четене и писане и набор от правила (алгоритъм), управляващи нейното поведение. Въпреки простотата си, тя е способна да моделира всяко изчисление, извършимо от реален компютър.
Недетерминистичната машина на Тюринг е абстрактно разширение на тази идея: при всяка стъпка тя може да „избере" едновременно между множество възможни преходи и да следва всички паралелно. Ако поне един от тези клонове стигне до верен отговор, машината се счита за успешна. Това е изцяло теоретична конструкция — никакъв реален компютър не работи така.
История: как се ражда проблемът?
Концепцията за недетерминизъм е въведена през 1959 г. от Майкъл Рабин и Дейна Скот в статията им „Крайни автомати и техните задачи за решения". Те описват недетерминистичен автомат като машина, която приема дадена входна лента, ако сред всички възможни комбинации от избори съществува поне една, водеща до крайно (приемащо) състояние.
Проблемът \(P\) срещу \(NP\) в съвременния му вид е формулиран от Стивън Кук в статията му от 1971 г. „Сложността на процедурите за доказване на теореми". Кук идентифицира и първата \(NP\)-пълна задача — задачата за удовлетворяемост на булеви формули (SAT).
Година по-късно, 1972 г., Ричард Карп разширява резултата на Кук, като доказва, че още 21 конкретни задачи са \(NP\)-пълни — сред тях задачата Graph Clique и задачата за Хамилтонов цикъл. Днес са известни хиляди \(NP\)-пълни задачи.
Защо \(NP\), а не нещо по-интуитивно?
Естествено е да се запитаме: защо класът \(NP\) е дефиниран чрез недетерминистични машини вместо чрез по-достъпното понятие за „проверяемост"? Причините са две.
Първо, недетерминистичните машини позволяват да се разсъждава за задачите от гледна точка на намирането на решение, а не само на неговата проверка — което дава по-широк теоретичен обхват. Второ, математическата структура на недетерминистичната машина на Тюринг е почти идентична с тази на детерминистичната: единствената разлика е, че функцията за преход към следващото състояние се заменя с релация — т.е. от едно състояние могат да водят много преходи вместо един. Тази минимална промяна на дефиницията е достатъчна, за да се получи качествено различно изчислително поведение.
Проблемът \(P\) срещу \(NP\) стои нерешен вече над 50 години. Повечето специалисти смятат, че \(P \neq NP\), но убедително доказателство — в нито една посока — все още не е намерено. Това прави въпроса не просто математически предизвикателен, а и философски дълбок: означава ли творчеството и откритието нещо принципно по-трудно от проверката?
Запишете урок
Индивидуални и групови онлайн уроци по математика за цялата страна
- ›НВО по математика след 7 клас
- ›НВО по математика след 10 клас
- ›Кандидатстудентски изпити по математика
- ›Прием в университети в чужбина (ISEE, SAT, A-Level)
- ›Усвояване на текущия учебен материал (всички класове)
- ›Студенти: Мат. анализ, Линейна алгебра, Аналитична геометрия, Диф. уравнения, Теория на вероятностите, Статистика и др.
Харесва ли ви съдържанието?
Ако тази статия ви е харесала, можете да подкрепите създаването на нови безплатни материали.
Коментари
Публикуване на коментар