Wersja z 07:48, 15 sty 2007 (edytuj) Chobot (dyskusja \| edycje) m (robot dodaje: ko:NP-난해) ← poprzednia edycja		Wersja z 11:22, 12 lut 2007 (edytuj) (anuluj edycję) 150.254.130.214 (dyskusja) Nie podano opisu zmian następna edycja →
'''Problem NP-trudny''' to taki [[problem ~~decyzyjny~~przeszukiwania (teoria obliczeń)\|problem decyzyjny]] do którego można w wielomianowym czasie (transformacją Turinga) zredukować ~~każdy~~pewien NP-zupełny [[problem decyzyjny (teoria obliczeń)\|problem decyzyjny]] z(a ~~[[Problem~~więc ~~NP\|NP]].~~trudny ~~Klasa~~problem ~~problemów NP-trudnych tym różni się od~~z 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.

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

Problem NP-trudny (edytuj)