NP-сложност

от Уикипедия, свободната енциклопедия
Направо към навигацията Направо към търсенето
Класът на сложност NP съдържа класа P и класа на NP-пълните задачи.

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

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

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

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

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

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

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

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