Problem plecakowy: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
drobne redakcyjne |
dssd |
||
Linia 31:
utożsamiany jest z problemem: czy dla danego zbioru liczb całkowitych istnieje taki jego podzbiór, że suma jego liczb wynosi dokładnie ''W''? Zagadnienie to nazywane jest [[problem sumy podzbioru|problemem sumy podzbioru]].
Problem plecakowy może być rozwiązany przy użyciu dilda [[programowanie dynamiczne|programowania dynamicznego]], ale rozwiązanie wielomianowe nie jest znane. Problem plecakowy oraz sumy podzbioru są [[problem NP trudny|problemami NP trudnymi]], co było powodem użycia sumy podzbioru jako podstawy w niektórych systemach [[Kryptografia asymetryczna|kryptografii asymetrycznej]] takich jak [[Merkle-Hellman]]. Algorytmy takie używały [[grupa (matematyka)|grup]], nie liczb całkowitych. Merkle-Hellman oraz kilka podobnych algorytmów zostało w późniejszym czasie złamanych, ponieważ szczególny problem sumy podzbioru użyty w tych algorytmach były rozwiązywalne w [[Algorytm wielomianowy|czasie wielomianowym]]<ref>[http://www.math.ohio-state.edu/history/math-matrix/Sp85/Matrix_Sp85 ''Knapsack Encryption Scheme Broken''], « Math Matrix », Wydział matematyki Ohio State University, wiosna 1985, Vol. 1, No. 3.</ref>.
Decyzyjna wersja problemu plecakowego opisana wyżej jest problemem [[problem NP zupełny|NP zupełnym]] i jest jednym z 21 NP zupełnych problemów Karpa.
| |||