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

[wersja nieprzejrzana]

Usunięta treść Dodana treść

Jednokolumnowy

Wersja z 11:22, 12 lut 2007

Problem NP-trudny to taki problem decyzyjny do którego można w wielomianowym czasie (transformacją Turinga) zredukować pewien NP-zupełny problem decyzyjny (a więc trudny problem z klasy 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 NP-zupełnych, że problemy w niej zawarte niekoniecznie są decyzyjne, to zanczy niekoniecznie są w NP.

Jeśli $P\neq NP$ , to problemy NP-trudne nie mają rozwiązań w czasie wielomianowym.

Szablon:Informatyka stub

@@ Linia 1: / Linia 1: @@
-'''Problem NP-trudny''' to taki [[problem decyzyjny (teoria obliczeń)|problem decyzyjny]] do którego można w wielomianowym czasie zredukować każdy [[problem decyzyjny (teoria obliczeń)|problem decyzyjny]] z [[Problem NP|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ą w [[Problem NP|NP]].
+'''Problem NP-trudny''' to taki [[problem przeszukiwania (teoria obliczeń)|problem decyzyjny]] 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-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.