Dyskusja:Problem NP-trudny: Różnice pomiędzy wersjami
Usunięta treść Dodana treść
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 4: | Linia 4: | ||
Problem NP-trudny należy do problemów przeszukiwania, których szczególna podklasą mogą być problemy decyzyjne ale też optymalizacyjne. |
Problem NP-trudny należy do problemów przeszukiwania, których szczególna podklasą mogą być problemy decyzyjne ale też optymalizacyjne. |
||
: I tak i nie. Możliwe są różne definicje. Zobacz też dyskusję [[:en:Talk:NP-hard#Not a decision problem|tutaj]] [[Wikipedysta:Kuszi|Kuszi]] 11:44, 12 lut 2007 (CET). |
: I tak i nie. Możliwe są różne definicje. Zobacz też dyskusję [[:en:Talk:NP-hard#Not a decision problem|tutaj]] [[Wikipedysta:Kuszi|Kuszi]] 11:44, 12 lut 2007 (CET). |
||
Polecam książkę: |
|||
Garey, Johnson, Computers and Intractability: A guide to the theory of NP-completeness. |
|||
W.H.Freeman & Co. N.Y. 1979 |
|||
albo |
|||
Złożoność obliczeniową Papadymitriou |
|||
Wersja z 15:41, 12 lut 2007
Poprzednia definicja była błędna. Twierdzi się, że problem NPh jest decyzyjny. To nie jest prawda. Do NP należą tylko problemy decyzyjne. Natomiast, problem NP-trudny nie musi należeć do klasy problemów decyzyjnych. Problem NP-trudny należy do problemów przeszukiwania, których szczególna podklasą mogą być problemy decyzyjne ale też optymalizacyjne.
- I tak i nie. Możliwe są różne definicje. Zobacz też dyskusję tutaj Kuszi 11:44, 12 lut 2007 (CET).
Polecam książkę: Garey, Johnson, Computers and Intractability: A guide to the theory of NP-completeness. W.H.Freeman & Co. N.Y. 1979 albo Złożoność obliczeniową Papadymitriou