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

Przejdź do nawigacji Przejdź do wyszukiwania
Usunięte 7 bajtów ,  15 lat temu
brak opisu edycji
Nie podano opisu zmian
Nie podano opisu zmian
 
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,
 
Oznacza* to, że problemProblem NP-trudny jest conajmniej tak trudny jak ten problem NP-zupełny,
a więc conajmniej tak trudny jak klasa problemów NP-zupełnych (najtrudniejszych w NP),
a więc conajmniej tak trudny jak cała klasa [[Problem NP|NP]].
 
* Ponieważ całą klasę [[Problem NP|NP]] można rozwiązać przez sprowadzenie do dowolnego problemu NP-zupełnego,
dlatego również całą klasę [[Problem NP|NP]] można rozwiązać przez sprowadzenie do dowolnego problemu NP-trudnego.
 
Anonimowy użytkownik

Menu nawigacyjne