NP-сложност
 | За информацията в тази статия или раздел не са посочени източници. Въпросната информация може да е непълна, неточна или изцяло невярна. Имайте предвид, че това може да стане причина за изтриването на цялата статия или раздел. |  |
Класът на сложност NP представлява множеството от всички задачи за разпознаване, за които е възможно да се провери за полиномиално време дали предложено решение наистина е решение. Съкращението NP идва от английския термин „nondeterministic polynomial time“, което значи „недетерминирано полиномиално време“.
В термините на машината на Тюринг могат да се формулират две определения, равносилни на горното:
- Една задача за разпознаване е от класа NP тогава и само тогава, когато съществува детерминирана машина на Тюринг, която за полиномиално време проверява дали предложено решение наистина е решение.
- Една задача за разпознаване е от класа NP тогава и само тогава, когато съществува недетерминирана машина на Тюринг, която за полиномиално време намира решение на задачата.
Класът на сложност P е част от NP, но освен него NP съдържа много други важни задачи. Най-трудните задачи в NP са т. нар. NP-пълни задачи; за тях не са известни алгоритми за намиране на решение в полиномиално време.
Някои задачи от класа NP:
- Намиране на простите множители на число (integer factorization problem);
- Изоморфизъм на графи – тази задача е от NP, но не е NP-пълна;
- Намиране на подмножество, сборът на чиито елементи е равен на дадено число – тази задача е NP-пълна;
- Удовлетворимост на булева функция – тази задача е NP-пълна;
- Вариант на задачата за търговски пътник: търси се маршрут с определена дължина, който минава по веднъж през всички върхове на даден граф.
Във всички тези примери проверката, дали предложено решение е наистина решение, отнема полиномиално време. За самото намиране на решение обаче не са известни алгоритми с полиномиална сложност по време в най-лошия случай.
Един от ключовите нерешени проблеми в теорията на изчислителната сложност и в информатиката като цяло е проблемът „P = NP“: съществуват ли алгоритми, които за полиномиално време могат да решат NP-пълна задача. Повечето специалисти смятат, че няма такива алгоритми.