Problem NP-trudny: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 1: | Linia 1: | ||
'''Problem NP-trudny'''(NPh) 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]]). |
'''Problem NP-trudny'''(NPh) 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]]). |
||
Wraz z definicjami klas problemów [[Problem NP|NP]] i NP-zupełnych, ma to następujące konsekwencje: |
Wraz z definicjami klas problemów [[Problem NP|NP]] i [[Problem NP zupełny|NP-zupełnych]], ma to następujące konsekwencje: |
||
Problem NP-zupełny można rozwiązać w wielomianowym czasie przez sprowadzenie do problemu NP-trudnego. |
Problem NP-zupełny można rozwiązać w wielomianowym czasie przez sprowadzenie do problemu NP-trudnego. |
||
Oznacza to, że problem NP-trudny jest conajmniej tak trudny jak ten problem NP-zupełny, |
Oznacza to, że problem NP-trudny jest conajmniej tak trudny jak ten problem NP-zupełny, |
||
| Linia 9: | Linia 9: | ||
dlatego również całą klasę [[Problem NP|NP]] można rozwiązać przez sprowadzenie do dowolnego problemu NP-trudnego. |
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 |
Klasa problemów NP-trudnych tym się też różni 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. |
Jeśli <math>P \neq NP</math>, to problemy NP-trudne nie mają rozwiązań w czasie wielomianowym. |
||
Wersja z 13:23, 12 lut 2007
Problem NP-trudny(NPh) to taki problem przeszukiwania, 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).
Wraz z definicjami klas problemów NP i NP-zupełnych, ma to następujące konsekwencje: Problem NP-zupełny można rozwiązać w wielomianowym czasie przez sprowadzenie 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 NP. Ponieważ całą klasę NP można rozwiązać przez sprowadzenie do dowolnego problemu NP-zupełnego, dlatego również całą klasę NP można rozwiązać przez sprowadzenie do dowolnego problemu NP-trudnego.
Klasa problemów NP-trudnych tym się też różni od klasy problemów NP-zupełnych, że problemy w niej zawarte niekoniecznie są decyzyjne, to znaczy niekoniecznie są w NP.
Jeśli , to problemy NP-trudne nie mają rozwiązań w czasie wielomianowym.
