Problem sumy podzbioru

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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 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.

Bibliografia[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]