problem P

Opis szczegółowy

Problem P - problem decyzyjny w którym znalezienie rozwiązania wymaga złożoności obliczeniowej wielomianowej.

Problem P należy do zbioru problemów NP. Z tego wynika, że:

• Sprawdzenie poprawności rozwiązania danego problemu jest możliwe w czasie wielomianowym;
• Znalezienie rozwiązania danego problemu jest możliwe w czasie wielomianowym.

Zagadnienia powiązane

problem decyzyjny	Opisanie problemu w taki sposób, że jego rozwiązaniem jest zawsze prawda lub fałsz. (pojęcie)
problem NP	Sprawdzenie poprawności danego rozwiązania wymaga złożoności obliczeniowej wielomianowej. (pojęcie)

Linki zewnętrzne

• http://en.wikipedia.org/wiki/P_versus_NP_problem
• http://pl.wikipedia.org/wiki/Problem_P