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

problem NP

[pojęcie] Sprawdzenie poprawności danego rozwiązania wymaga złożoności obliczeniowej wielomianowej.

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

Linki zewnętrzne