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

problem NP-Trudny

[pojęcie] Znalezienie rozwiązania problemu nie jest możliwe ze złożonością obliczeniową wielomianową.

Opis szczegółowy

Problem NP-Trudny - problem obliczeniowy dla którego znalezienie rozwiązania problemu nie jest możliwe ze złożonością obliczeniową wielomianową oraz sprawdzenie rozwiązania problemu jest co najmniej tak trudne jak każdego innego problemu NP. Problemy NP-Trudne obejmują zarówno problemy decyzyjne jak również problemy przeszukiwania czy też problemy optymalizacyjne.

Problem zaliczany jest do NP-Trudnych jeżeli sprawdzenie poprawności rozwiązania wymaga złożoności obliczeniowej co najmniej wielomianowej i jednocześnie spełniony jest co najmniej jeden z poniższych warunków:
  • rozważany problem NP jest problemem NP-Zupełnym;
  • rozważany jest problem przeszukiwania;
  • rozważany jest problem optymalizacyjny;
  • znalezienie rozwiązania problemu nie jest możliwe ze złożonością wielomianową.

Dodatkowe informacje

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

Zagadnienia powiązane

problem NPSprawdzenie poprawności danego 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 decyzyjnyOpisanie problemu w taki sposób, że jego rozwiązaniem jest zawsze prawda lub fałsz. (pojęcie)
problem optymalizacyjnyOpisanie problemu w taki sposób, że jego rozwiązaniem jest najlepszy możliwy do uzyskania wynik. (pojęcie)
problem przeszukiwaniaOpisanie problemu w taki sposób, że jego rozwiązaniem jest zbiór wyników spełniających warunki wynikające z opisu problemu. (pojęcie)

Linki zewnętrzne