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

• Thomas H Cormen, Charles E Leiserson, Ronald L Rivest: Wprowadzenie do algorytmów. Warszawa: Wydawnictwa Naukowo-Techniczne, 2003. ISBN 83-204-2800-9. Brak numerów stron w książce

Linki zewnętrzne

• Suma podzbioru na stronie wazniak.mimuw.edu.pl