problem NP-Trudny

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 NP	Sprawdzenie poprawności danego 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 decyzyjny	Opisanie problemu w taki sposób, że jego rozwiązaniem jest zawsze prawda lub fałsz. (pojęcie)
problem optymalizacyjny	Opisanie problemu w taki sposób, że jego rozwiązaniem jest najlepszy możliwy do uzyskania wynik. (pojęcie)
problem przeszukiwania	Opisanie 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

• http://en.wikipedia.org/wiki/NP-hard
• http://pl.wikipedia.org/wiki/Problem_NP-trudny
• http://xlinux.nist.gov/dads/HTML/nphard.html