Problem P
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: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • 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 {-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.
- p
- d
- e
Uważane za wykonalne |
|
---|---|
Podejrzewane o niewykonalność |
|
Uważane za niewykonalne |
|
Hierarchie klas |
|
Rodziny klas |
|