NP-сложност: Разлика между версии

[[File:Complexity classes.svg|thumb|250px|МножествоКласът на задачите отсложност '''NP-сложност.''' Неговисъдържа подмножествакласа са'''P''' множестватаи класа на задачите от сложност P и '''NP'''-пълните задачи.]]

'''ЗадачитеКласът сна NP-сложност NP''' сепредставлява дефиниратмножеството катоот [[класвсички назадачи сложност|клас]]за задачиразпознаване, за които е възможно вда се провери за [[полиномиално време]] да се провери дали даден кандидат запредложено решение наистина е решение. АбревиатуратаСъкращението '''NP''' идва от английския термин „Nondeterministic„nondeterministic Polynomialpolynomial time“, „недетерминистичнокоето значи „недетерминирано полиномиално време“.

В термините на [[машина на Тюринг|машината на Тюринг]] следнитемогат дведа дефинициисе наформулират задача от NP-сложностдве саопределения, равносилни на горнатагорното:

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

* СъществуваЕдна задача за разпознаване е от класа '''NP''' тогава и само тогава, когато съществува [[недетерминистична машина на Тюринг|недетерминирана машина на Тюринг,]], която за полиномиално време намира решение на задачата за полиномиално време.

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

ПримериНякои за NP-задачи саот следнитекласа '''NP''':

* Задача за [[изоморфизъмИзоморфизъм]] междуна [[граф (математика)|графи]] (''graph— isomorphismтази problemзадача е от ''') — NP-задача''', но не ие NP-пълна;

* Намиране на подмножество на числово множество, суматасборът на чиито елементи е равнаравен на дадено число (''subset sum problem'') — тази задача е и NP-пълна;

* [[Удовлетворимост на булева функция]] (''Boolean satisfiability problem'') — тази задача е и NP-пълна;

* Вариант на [[задача за търговски пътник|задачата за търговски пътник:]], при койтотърси се търси маршрут с определена дължина, който минава по веднъж през всички възливърхове на даден граф.

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

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

* [[Проблем „P = NP“|Проблем „'''P = NP'''“]]