Problem plecakowy: Różnice pomiędzy wersjami

Dodane 43 bajty ,  7 miesięcy temu
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.8
m (WP:SK+Bn)
(Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.8)
utożsamiany jest z problemem: czy dla danego zbioru liczb całkowitych istnieje taki jego podzbiór, że suma jego liczb wynosi dokładnie <math>W</math>? Zagadnienie to nazywane jest [[problem sumy podzbioru|problemem sumy podzbioru]].
 
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 klucza publicznego|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>[https://web.archive.org/web/20071122014915/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.
253 733

edycje