Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Opracował: Piotr DejaVu Szawdyński
Pojęcia

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 decyzyjnyOpisanie problemu w taki sposób, że jego rozwiązaniem jest zawsze prawda lub fałsz. (pojęcie)
problem NPSprawdzenie poprawności danego rozwiązania wymaga złożoności obliczeniowej wielomianowej. (pojęcie)
problem NP-TrudnyZnalezienie rozwiązania problemu nie jest możliwe ze złożonością obliczeniową wielomianową. (pojęcie)

Linki zewnętrzne