NP-сложност

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене
Множество на задачите от NP-сложност. Негови подмножества са множествата на задачите от сложност P и 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-задачи. Широко разпространеното схващане е, че такива алгоритми не съществуват.

Вижте също[редактиране | edit source]