Problem sumy podzbioru
Z Wikipedii
Problem sumy podzbioru jest jednym z ważniejszych problemów w teorii złożoności oraz kryptografii. Treść problemu jest następująca: Mając dany skończony zbiór liczb całkowitych, czy istnieje pewien niepusty podzbiór którego suma jest równa 0? Dla przykładu: odpowiedź dla zbioru { −7, −3, −2, 5, 8} jest pozytywna, ponieważ podzbiór { −3, −2, 5} sumuje się do zera. Problem należy do klasy problemów NP zupełnych i jest prawdopodobnie jednym z najprostszych do opisania.
Można również spotkać następującą definicje problemu Mając dany zbiór liczb całkowitych oraz liczbę s, czy istnieje pewien niepusty podzbiór którego suma jest równa s?. Problem sumy podzbioru może być rozpatrywany jako szczególny przypadek problemu plecakowego. Jednym z szczególnych przypadków problemu sumy podzbioru jest problem podziału, w którym s jest równe połowie sumy wszystkich liczb ze zbioru.
[edytuj] Bibliografia
- Thomas H Cormen, Charles E Leiserson, Ronald L Rivest: Wprowadzenie do algorytmów. Warszawa: Wydawnictwa Naukowo-Techniczne, 2003. ISBN 83-204-2800-9.
[edytuj] Linki zewnętrzne
- Algorytm (złożoność wykładnicza) rozwiązujący problem sumy podzbioru
- Suma podzbioru na stronie wazniak.mimuw.edu.pl