Problem NP-trudny (NPH)
Problem NP-trudny to problem obliczeniowy, którego rozwiązanie jest co najmniej tak trudne, jak rozwiązanie każdego problemu z klasy NP. Formalnie, problem NP-trudny π₂ jest definiowany jako taki, do którego istnieje redukcja wielomianowa z problemu NP-zupełnego π₁.
Reklama
Oznacza to, że jeśli potrafimy rozwiązać problem NP-trudny π₂, możemy również rozwiązać problem NP-zupełny π₁ w czasie wielomianowym, korzystając z hipotetycznej procedury H, która wykonuje tę redukcję.
NP-trudność można również zdefiniować w kontekście języków formalnych. Problemy NP-trudne obejmują różne typy, w tym decyzyjne, przeszukiwania i optymalizacyjne.
Reklama
Reklama
Konsekwencje definicji
- Optymalizacyjny problem, którego wersja decyzyjna jest NP-zupełna, jest NP-trudny.
- Problem NP-trudny π₂ jest co najmniej tak trudny jak problem NP-zupełny π₁.
- Jeśli P ≠ NP, problemy NP-trudne nie mają rozwiązań w czasie wielomianowym.
- Jeżeli problem π₂ należy do klasy NP, to jest również NP-zupełny.
Przykłady problemów NP-trudnych
- Problem komiwojażera
- Problem plecakowy
- Problem zbioru niezależnego
- Problem zbioru wierzchołków rozrywających cykle
