NP-трудни и NP-пълни проблеми — определение и примери

Ясно обяснение на NP-трудни и NP-пълни проблеми: дефиниции, ключови примери (пътуващ търговец) и разликата между проверка и решаване.

NP-труден (NP-hard) проблем е проблем с отговор "да/не" (решаваем чрез език на решенията), за който намирането на решение е поне толкова трудно, колкото намирането на решение за всеки проблем, чието решение може бързо да бъде проверено като вярно. Формално се казва, че проблем B е NP-труден, ако за всеки проблем A в NP съществува полиномиално време много-към-едно свиване (reduction) f, така че x ∈ A точно тогава, когато f(x) ∈ B. По този начин всеки алгоритъм за B може да се използва (чрез предобработка на входа) за решаване на всеки проблем от NP. Някои NP-трудни проблеми са такива, чието решение може да се провери бързо — те принадлежат и на класа NP — а някои не принадлежат на NP (например са неразрешими или излизат извън рамките на бързо проверяемите решения).

NP-пълни проблеми

NP-пълен (NP-complete) проблем е проблем, който е едновременно в NP и NP-труден. Това означава, че неговите решения могат да се проверят бързо (имаме полиномиален верификатор с подходящ сертификат), и в същото време всеки друг проблем в NP може да бъде полиномиално редуциран към него. Следователно, ако се намери полиномиален алгоритъм за който и да е NP-пълен проблем, това ще покаже, че P = NP и всички проблеми в NP могат да се решават в полиномиално време.

Какво значи "може да бъде проверено бързо" (включване в NP)

Класът NP съдържа всички езикови проблеми (решения "да/не"), за които съществува верификатор, работещ за полиномиално време: ако отговорът е "да", съществува кратък (полиномен по размера на входа) свидетел (certificate), който позволява на алгоритъм да провери коректността на отговора за полиномиално време. Това не означава непременно, че има бърз алгоритъм за намиране на такъв свидетел; само че веднага щом го имаш, можеш бързо да провериш.

Примери

Пример за проблем, който е поне толкова труден за решаване, колкото всеки друг проблем, за който можем бързо да проверим решенията, и който също така е бързо проверим (той е едновременно NP-труден и NP):

Пътуващ търговец иска да посети 100 града, като пътува с кола, започвайки и завършвайки пътуването си у дома. Той разполага с ограничен запас от бензин, така че може да измине общо само 10 000 км. Той иска да знае дали може да посети всички градове, без да изчерпи бензина.

Хората не знаят как да решат този проблем по-бързо от тестването на всеки възможен отговор, но ако се намери решение (обиколка), която позволява на продавача да направи това, можем да използваме алгоритъм за проверка дали то е вярно. Този проблем е известен още като проблем на пътуващия продавач (решението по-горе е формулировка на решението като решение-да/не: съществува ли обиколка със сумарна дължина ≤ 10 000 km?). Всяка от тези формулировки има естествена версия като решение-да/не и е NP-пълен (в стандартните формулировки на TSP като решение-да/не с граници на разстоянието).

Пример за задача, която може да бъде много по-трудна и да не принадлежи на NP (не може да бъде проверена бързо):

Да разгледаме прост програмен фрагмент:

while(true){ continue; }

Въпросът: ако някой стартира програма, която просто върви така, тя ще работи ли вечно? Тази форма на проблема попада в семейството на проблемите за спиране и поведение на програмите — такива проблеми могат да бъдат неразрешими (т.е. няма алгоритъм, който да дава правилен отговор за всички входове) и също не подлежат на бърза проверка в смисъла на NP. Това илюстрира, че някои задачи от изчислителната теория са извън класа NP; по-общо, NP-трудни проблеми не е задължително да принадлежат на NP.

Още важни бележки

• Редукции: Обикновено когато се говори за NP-трудност и NP-пълнота се използват полиномиални много-към-едно редукции (Karp-редукции). Понякога се използват и по-силни или по-слаби видове редукции (напр. Turing-редукции), затова винаги е добре да се уточни вида на редукцията при формални твърдения.
• Клас P срещу NP: Въпросът дали P = NP (дали всеки проблем, чиято коректност може да се провери бързо, може и да се реши бързо) е една от големите нерешени задачи в информатиката. Ако се окаже, че някой NP-пълен проблем е в P, това би означавало P = NP и би дала бързи алгоритми за всички проблеми в NP.
• NP-трудни извън NP: Някои NP-трудни задачи могат да бъдат по-сложни от NP — те могат да бъдат неразрешими или да изискват по-мощни верификатори. Поради това класификацията "NP-труден" само казва, че задачата е не по-лесна от всички в NP; тя не дава автоматично информация дали задачата е в NP.
• Практически подходи: Много NP-трудни и NP-пълни проблеми се решават в практиката чрез приблизителни алгоритми, хедристики, мета-евристики, експоненциални алгоритми с оптимизации или алгоритми за конкретни случаи (напр. параметризирана сложност). За реални входни размери често се намират полезни решения въпреки теоретичната сложност.

Често срещани NP-пълни примери

• Boolean SAT (и 3-SAT) — Cook–Levin теорема показа, че SAT е NP-пълен.
• Проблем на пътуващия продавач (TSP) в решение-форма (справяне с дължина ≤ K).
• Hamiltonian Cycle, Clique, Vertex Cover, Subset Sum, Knapsack (решение/решета форма) и много други.

В заключение: NP-трудност означава "поне толкова трудно, колкото най-трудните проблеми в NP" (по отношение на полиномиални редукции). NP-пълнота добавя изискването проблемът да бъде и в NP. Разбирането на тези дефиниции е важно както за теоретичната информатика, така и за практическото проектиране на алгоритми и избор на техники за справяне с трудни задачи.

Въпроси и отговори

Въпрос: Какво е NP-труден проблем?

Въпрос: Може ли бързо да се провери работещо решение за всички NP-трудни проблеми?

Въпрос: Как се нарича категорията за NP-трудни проблеми, които са и NP-проблеми?

В: Всички ли NP-трудни проблеми са NP-пълни?

Въпрос: Лесно ли се решават NP-трудните проблеми?

В: Има ли някакви предимства при решаването на NP-трудни задачи?

В: Има ли текущи изследвания в областта на решаването на NP-трудни задачи?

Търсене по буква