Problem NP-trudny
problem obliczeniowy / Z Wikipedii, wolnej encyclopedia
Drogi AI, mówmy krótko, odpowiadając po prostu na te kluczowe pytania:
Czy możesz wymienić najważniejsze fakty i statystyki dotyczące Problem NP-trudny?
Podsumuj ten artykuł dla 10-latka
Problem NP-trudny (NPH, ang. NP-Hard) – problem obliczeniowy, którego rozwiązanie jest co najmniej tak trudne, jak rozwiązanie każdego problemu z klasy NP (całej klasy NP).
Formalna definicja problemu NP-trudnego jest następująca:
- Problem
jest NP-trudny, jeżeli pewien problem NP-zupełny
jest do niego redukowalny wielomianową transformacją Turinga.
Innymi słowy, problem NP-zupełny można rozwiązać w wielomianowym czasie algorytmem rozwiązującym problem NP-trudny
przez wykorzystanie hipotetycznej procedury
sprowadzającej problem NP-zupełny
do problemu NP-trudnego
jeżeli tylko
daje się wykonać w wielomianowym czasie. NP-trudność można zdefiniować także w kategorii języków formalnych (a nie problemów). Do klasy problemów NP-trudnych mogą należeć problemy różnego typu: decyzyjne, przeszukiwania, optymalizacyjne.
Wraz z definicjami klas problemów NP i NP-zupełnych ma to następujące konsekwencje:
- problem optymalizacyjny, którego wersja decyzyjna jest NP-zupełna, jest problemem NP-trudnym;
- NP-trudny problem
jest co najmniej tak trudny, jak problem
- ponieważ
jest problemem NP-zupełnym, toteż należy on do problemów najtrudniejszych w klasie NP, dlatego NP-trudny problem
jest co najmniej tak trudny, jak cała klasa NP;
- ponieważ wszystkie problemy NP-zupełne transformują się wzajemnie do siebie (zwykłą) transformacją wielomianową (nie Turinga), to również wszystkie problemy NP-zupełne można rozwiązać przez redukcję do NP-trudnego problemu
- ponadto, jeśli
to problemy NP-trudne nie mają rozwiązań w czasie wielomianowym, natomiast rozstrzygnięcie
nie przesądza o wielomianowej rozwiązywalności wszystkich problemów NP-trudnych;
- jeżeli problem
należy do klasy NP, to
jest też problemem NP-zupełnym (gdyż wraz z istniejącą transformacją Turinga spełnia definicję problemu NP-zupełnego).