Ten artykuł od 2016-11 wymaga zweryfikowania podanych informacji.

Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Google Books • Google Scholar • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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.