brak opisu edycji
Nie podano opisu zmian |
Nie podano opisu zmian |
||
|
'''Problem NP-trudny'''(NPh) to taki [[problem przeszukiwania (teoria obliczeń)|problem przeszukiwania]], do którego można w wielomianowym czasie (transformacją Turinga) zredukować pewien NP-zupełny [[problem decyzyjny (teoria obliczeń)|problem decyzyjny]] (a więc trudny problem z klasy [[Problem NP|NP]]).
Wraz z definicjami klas problemów [[Problem NP|NP]] i [[Problem NP zupełny|NP-zupełnych]], ma to następujące konsekwencje:
Problem NP-zupełny można rozwiązać w wielomianowym czasie przez sprowadzenie do problemu NP-trudnego.
Oznacza to, że problem NP-trudny jest conajmniej tak trudny jak ten problem NP-zupełny,
dlatego również całą klasę [[Problem NP|NP]] można rozwiązać przez sprowadzenie do dowolnego problemu NP-trudnego.
Klasa problemów NP-trudnych tym
Jeśli <math>P \neq NP</math>, to problemy NP-trudne nie mają rozwiązań w czasie wielomianowym.
| |||