Problem plecakowy: Różnice pomiędzy wersjami

Problem plecakowy może być rozwiązany przy użyciu [[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>.

 

 

== Realizacje algorytmu ==