Problem P: Różnice pomiędzy wersjami

[wersja przejrzana][wersja przejrzana]
Usunięta treść Dodana treść
bład logiczny
m int.
Linia 1:
'''Problem P''' ([[Język angielski|ang.]] ''deterministic polynomial'' - deterministycznie [[wielomian]]owy) to [[problem decyzyjny (teoria obliczeń)|problem decyzyjny]], dla którego rozwiązanie można znaleźć w czasie wielomianowym.
 
Różnica pomiędzy problemami P i [[problem NP|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żmyPrzykładowy 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 istnieje problem NP będący P. Jest to jedno z wielkich nierozwiązanych dotychczas zagadnień informatyki.