Problem P: Różnice pomiędzy wersjami
[wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
Zjadło komuś jedno "nie" w przedostatnim zdaniu, poprawiłem. |
drobne redakcyjne |
||
Linia 1:
'''Problem P''' (
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ść.
Linia 6:
:''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})
Każdy problem P jest NP, jednak nie wiadomo, czy istnieje problem NP
[[Kategoria:Teoria obliczeń]]
|