Problema delle somme parziali

Il problema delle somme parziali è uno dei problemi NP-completi. Esso consiste nel determinare, dato un insieme finito di numeri interi, se ne esiste un sottoinsieme tale che la somma di suoi elementi sia $0$. Si può notare che è semplice determinare se un sottoinsieme sia o meno la soluzione del problema, ma non è noto alcun metodo per trovare una soluzione che sia sensibilmente più veloce di provare tutti i possibili sottoinsiemi tranne i due che contengono tutti numeri concordi (tutti negativi o tutti positivi), quelli formati da un solo numero negativo e da tutti numeri positivi maggiori in valore assoluto al numero negativo e quelli formati da un solo numero positivo e da tutti numeri negativi maggiori in valore assoluto al numero positivo. La scoperta di un metodo "veloce" per risolvere questo problema, darebbe anche la soluzione per uno dei millennium problems (P vs NP, formulato da Stephen Cook e Leonid Levin nel 1971), per il quale l'istituto Clay Mathematics ha messo in palio un milione di dollari.