Problem NP

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Problem NP (niedeterministycznie wielomianowy, ang. nondeterministic polynomial) to 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ładowo rozważmy 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 PNP, ponieważ można je sprawdzić w czasie wielomianowym. Innymi słowy, klasa P zawiera się nieostro w NP (P \subseteq NP). Nie wiadomo natomiast, czy istnieje problem NP, który nie jest w klasie P (czyli, czy P rożni się od NP, lub inaczej P\neq NP lub inaczej P\subset NP). Jest to jedno z wielkich nierozwiązanych zagadnień informatyki.

Zobacz też[edytuj | edytuj kod]