Problem P

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Problem P (ang. deterministic polynomial, deterministycznie wielomianowy) – 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ładowy problem:

Czy jakikolwiek podzbiór zadanego zbioru {-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żna w liniowym, czyli również wielomianowym, czasie sprawdzić czy sumuje się do zera. Jest to zatem problem NP.

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

Zobacz też[edytuj | edytuj kod]

  • klasa złożoności