Problem NP 1971r. | problemy-milenijne

Problem NP-1971r.

Stan na dzisiaj

Problem NP (ang. nondeterministic polynomial, niedeterministycznie wielomianowy) – problem decyzyjny, dla którego rozwiązanie można zweryfikować w czasie wielomianowym. Równoważna definicja mówi, że problem jest w klasie NP, jeśli może być rozwiązany w wielomianowym czasie na niedeterministycznej maszynie Turinga.

Różnica pomiędzy problemami P i NP polega na tym, że w przypadku P znalezienie rozwiązania ma mieć złożoność wielomianową, podczas gdy dla NP sprawdzenie podanego z zewnątrz rozwiązania ma mieć taką złożoność.

Przykładowy problem:

Czy jakikolwiek niepusty podzbiór zadanego zbioru (np. {-2,6,-3,72,10,-11}) sumuje się do zera?

Trudno znaleźć rozwiązanie tego zagadnienia w czasie wielomianowym. Nasuwający się algorytm sprawdzenia wszystkich możliwych podzbiorów ma złożoność wykładniczą ze względu na liczebność zbioru. Nie wiadomo zatem, czy problem ten jest klasy P. Na pewno natomiast uzyskawszy z zewnątrz kandydata na rozwiązanie (np. {-2,6,-3,10,-11}) możemy w liniowym (a zatem wielomianowym) czasie sprawdzić, czy sumuje się do zera. Jest to zatem problem NP.

W szczególności wszystkie problemy klasy P są NP, ponieważ można je sprawdzić w czasie wielomianowym. Innymi słowy, klasa P zawiera się nieostro w NP. Nie wiadomo natomiast czy istnieje problem NP, który nie jest w klasie P.

Diagram Eulera dla problemów P, NP, NP-zupełnych i NP-trudnych. Istnienie problemów wewnątrz NP, ale nie należących ani do P, ani do NP-zupełnych, przy założeniu, że P≠NP, zostało udowodnione przez Ladnera [1].

Brak pełnego rozwiązania

Istnieją wyniki w szczególnych przypadkach. Brak pełnego rozwiązania.

Dowiedz się więcej