Problem NP-trudny: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
Nie podano opisu zmian |
Nie podano opisu zmian |
||
Linia 2:
Oznacza to, że problem NP-zupełny można rozwiązać przez sprowadzenie w wielomianowym czasie do problemu NP-trudnego.
Oznacza to, że problem 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.
Klasa problemów NP-trudnych tym różni się też tym od klasy problemów [[Problem NP zupełny|NP-zupełnych]], że problemy w niej zawarte niekoniecznie są decyzyjne, to znaczy niekoniecznie są w [[Problem NP|NP]].
| |||