NP-сложност
Задачите с NP-сложност се дефинират като клас задачи, за които е възможно в полиномиално време да се провери дали даден кандидат за решение наистина е решение. Абревиатурата NP идва от английския термин „Nondeterministic Polynomial time“, „недетерминистично полиномиално време“.
В термините на машината на Тюринг следните две дефиниции на задача от NP-сложност са равносилни на горната:
- Съществува детерминистична машина на Тюринг, която за полиномиално време проверява дали даден кандидат за решение наистина е решение.
- Съществува недетерминистична машина на Тюринг, която намира решение на задачата за полиномиално време.
Класът на сложност P се включва като подмножество на NP-класа, но освен него NP съдържа много други важни задачи, най-трудните от които са NP-пълните задачи, за които не са известни алгоритми за решение в полиномиално време.
Примери за NP-задачи са следните:
- Намиране на простите множители на число (integer factorization problem);
- Задача за изоморфизъм между графи (graph isomorphism problem) — NP-задача, но не и NP-пълна;
- Намиране на подмножество на числово множество, сумата на чиито елементи е равна на дадено число (subset sum problem) — тази задача е и NP-пълна;
- Удовлетворимост на булева функция (Boolean satisfiability problem) — тази задача е и NP-пълна;
- Вариант на задачата за търговски пътник, при който се търси маршрут с определена дължина, който минава през всички възли на даден граф.
Във всички тези примери проверката дали намерен кандидат за решение е наистина решение отнема полиномиално време. Проблемът при тези задачи е, че намирането на кандидат за решение не е толкова лесно колкото изглежда и обикновено изисква пълно изчерпване, което е проблем с експоненциална сложност.
Един от ключовите нерешени проблеми в теорията на изчислителната сложност и в информатиката като цяло е проблемът „P = NP“, който търси такива алгоритми от полиномиална сложност за решение на NP-пълните задачи, а оттам и за всички NP-задачи. Широко разпространеното схващане е, че такива алгоритми не съществуват.
