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 1:
'''Problem NP-trudny''' 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]]).
Oznacza to, że problem NP-
Oznacza to, że problem NP-trudny jest conajmniej tak trudny jak ten problem NP-zupełny,
Klasa problemów NP-trudnych tym różni się 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]].▼
a więc conajmniej tak trudny jak klasa problemów NP-zupełnych (najtrudniejszych w NP).
▲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]].
Jeśli <math>P \neq NP</math>, to problemy NP-trudne nie mają rozwiązań w czasie wielomianowym.
| |||