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ść.
:''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
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.
|