problem NP-Zupełny

[pojęcie] 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ą.

Opis szczegółowy

Problem NP-Zupełny - problem decyzyjny, którego rozwiązanie nie jest możliwe w czasie wielomianowym.

Problem NP-Zupełny należy do zbioru problemów NP jak również do zbioru problemów NP-Trudnych. Z tego wynika, że:

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

Dodatkowe informacje

Problemów NP-Zupełnych nie da się rozwiązać w czasie wielomianowym (teza ta na dzień dzisiejszy nie została ani dowiedziona ani obalona).

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)
problem NP-Trudny	Znalezienie rozwiązania problemu nie jest możliwe ze złożonością obliczeniową wielomianową. (pojęcie)

Linki zewnętrzne

Wszystkie teksty są chronione prawami autorskimi. Kopiowanie lub rozpowszechnianie treści poza niniejszym serwisem jest zabronione.

Powyższe ograniczenie nie dotyczy autora opracowania, któremu przysługuje prawo do rozpowszechniania własnego tekstu wedle własnego uznania.