Problem sumy podzbioru
Problem sumy podzbioru – jeden z ważniejszych problemów w teorii złożoności oraz kryptografii.
Treść problemu:
- Mając dany skończony zbiór liczb całkowitych rozstrzygnąć, czy istnieje niepusty jego podzbiór sumujący się do zera.
Np. dla zbioru {−7, −3, −2, 5, 8} odpowiedź 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 rozstrzygnąć, czy istnieje niepusty jego podzbiór sumujący się do s..
Problem sumy podzbioru może być rozpatrywany jako szczególny przypadek problemu plecakowego. Jednym ze 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.
Bibliografia edytuj
- Thomas H Cormen, Charles E Leiserson, Ronald L Rivest: Wprowadzenie do algorytmów. Warszawa: Wydawnictwa Naukowo-Techniczne, 2003. ISBN 83-204-2800-9.