Loading AI tools
Da Wikipedia, l'enciclopedia libera
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 . 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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.