Problem P

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Problem P (ang. deterministic polynomial - deterministycznie wielomianowy) to problem decyzyjny, dla którego rozwiązanie można znaleźć w czasie wielomianowym.

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 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 (czyli wielomianowym) czasie sprawdzić, czy sumuje się do zera. Jest to zatem problem NP.

Każdy problem P jest NP, jednak nie wiadomo, czy każdy problem NP jest P. Jest to jedno z wielkich nierozwiązanych dotychczas zagadnień informatyki.