Problem NP-trudny: Różnice pomiędzy wersjami

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:
Anonimowy użytkownik