Problem podzbioru o zadanej sumie

Problem podzbioru o zadanej sumie jest jednym z ważnych, a zarazem uważanych za bardzo trudne (NP-zupełny) zagadnień w informatyce. Problem wygląda następująco: mamy dany skończony zbiór liczb całkowitych S oraz liczbę n. Pytanie brzmi: czy istnieje niepusty podzbiór T zbioru S taki, że suma elementów zbioru T wynosi S? Innymi słowy, czy dla danego zbioru istnieje jego podzbiór o zadanej sumie?

Łatwo można udowodnić, że w problemie podzbioru można się ograniczyć do n=0.

Przykładowa instancja tego problemu: dla S={-7,-3,-2,5,8} i n=0 odpowiedź brzmi TAK, poszukiwany podzbiór T={-3,-2,5}.

Problem podzbioru o zadanej sumie ma bardzo ważne zastosowania praktyczne - np. w zaganieniach optymalizacyjnych, czy w kryptografii.