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

Dodane 38 bajtów ,  15 lat temu
brak opisu edycji
Nie podano opisu zmian
Nie podano opisu zmian
* Problem NP-zupełny można rozwiązać w wielomianowym czasie przez sprowadzenie do problemu NP-trudnego.
 
* Problem NP-trudny jest conajmniej tak trudny jak ten problem NP-zupełny, a więc conajmniej tak trudny jak klasa problemów [[Problem NP zupełny|NP-zupełnych]] (najtrudniejszych w [[Problem NP|NP]]), a więc conajmniej tak trudny jak cała klasa [[Problem NP|NP]].
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