Problem P

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 n-elementowego sumuje się do zera?

Trudno znaleźć rozwiązanie tego zagadnienia w czasie wielomianowym, jeżeli liczebność zbioru jest duża. 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.) można w liniowym (czyli również wielomianowym) czasie sprawdzić czy sumuje się do zera. Jest to zatem problem NP.

Np. mając zbiór {-2,6,-3,72,10,-11} łatwo spostrzec, że podzbiór {-2,6,-3,10,-11} sumuje się do zera. Jednak dla zbiorów o dużej liczbie elementów staje się to wręcz niewykonalne przy istniejących mocach obliczeniowych komputerów.

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.