problem NP

Opis szczegółowy

Problem NP - problem decyzyjny w którym sprawdzenie poprawności określonego rozwiązania wymaga złożoności obliczeniowej wielomianowej.

Z powyższego stwierdzenia wynika więc, że znalezienie rozwiązania dla problemów NP wymaga złożoności obliczeniowej co najmniej wielomianowej.

Zagadnienia powiązane

problem decyzyjny	Opisanie problemu w taki sposób, że jego rozwiązaniem jest zawsze prawda lub fałsz. (pojęcie)
problem P	Znalezienie rozwiązania wymaga złożoności obliczeniowej wielomianowej. (pojęcie)
problem NP-Zupełny	Sprawdzenie poprawności danego rozwiązania wymaga złożoności obliczeniowej wielomianowej oraz nie jest możliwe rozwiązanie problemu ze złożonością obliczeniową wielomianową. (pojęcie)
problem NP-Trudny	Znalezienie rozwiązania problemu nie jest możliwe ze złożonością obliczeniową wielomianową. (pojęcie)

Linki zewnętrzne

• http://pl.wikipedia.org/wiki/Problem_NP