NP-сложност

Класът на сложност NP представлява множеството от всички задачи за разпознаване, за които е възможно да се провери за полиномиално време дали предложено решение наистина е решение. Съкращението NP идва от английския термин „nondeterministic polynomial time“, което значи „недетерминирано полиномиално време“.

В термините на машината на Тюринг могат да се формулират две определения, равносилни на горното:

• Една задача за разпознаване е от класа NP тогава и само тогава, когато съществува детерминирана машина на Тюринг, която за полиномиално време проверява дали предложено решение наистина е решение.
• Една задача за разпознаване е от класа NP тогава и само тогава, когато съществува недетерминирана машина на Тюринг, която за полиномиално време намира решение на задачата.

Класът на сложност P е част от NP, но освен него NP съдържа много други важни задачи. Най-трудните задачи в NP са т. нар. NP-пълни задачи; за тях не са известни алгоритми за намиране на решение в полиномиално време.

Някои задачи от класа NP:

• Намиране на простите множители на число (integer factorization problem);
• Изоморфизъм на графи – тази задача е от NP, но не е NP-пълна;
• Намиране на подмножество, сборът на чиито елементи е равен на дадено число – тази задача е NP-пълна;
• Удовлетворимост на булева функция – тази задача е NP-пълна;
• Вариант на задачата за търговски пътник: търси се маршрут с определена дължина, който минава по веднъж през всички върхове на даден граф.

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

Един от ключовите нерешени проблеми в теорията на изчислителната сложност и в информатиката като цяло е проблемът „P = NP“: съществуват ли алгоритми, които за полиномиално време могат да решат NP-пълна задача. Повечето специалисти смятат, че няма такива алгоритми.