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

Dodane 293 bajty ,  15 lat temu
brak opisu edycji
m (robot dodaje: ko:NP-난해)
Nie podano opisu zmian
'''Problem NP-trudny''' to taki [[problem decyzyjnyprzeszukiwania (teoria obliczeń)|problem decyzyjny]] do którego można w wielomianowym czasie (transformacją Turinga) zredukować każdypewien NP-zupełny [[problem decyzyjny (teoria obliczeń)|problem decyzyjny]] z(a [[Problemwięc NP|NP]].trudny Klasaproblem problemów NP-trudnych tym różni się odz klasy problemów [[Problem NP zupełny|NP-zupełnych]],). że problemy w niej zawarte niekoniecznie są w [[Problem NP|NP]].
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).
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 zanczy niekoniecznie są w [[Problem NP|NP]].
 
Jeśli <math>P \neq NP</math>, to problemy NP-trudne nie mają rozwiązań w czasie wielomianowym.
Anonimowy użytkownik