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.