Immagina di essere un ladro che ruba una mostra museale di gioielli stuzzicanti, geodi e gemme rare. Sei nuovo in questo, quindi hai portato solo uno zaino. Il tuo obiettivo dovrebbe essere quello di farla franca con gli oggetti più preziosi senza sovraccaricare la borsa fino a quando non si rompe o diventa troppo pesante da trasportare. Come si fa a scegliere tra gli oggetti per massimizzare il vostro bottino? Potresti elencare tutti gli artefatti e i loro pesi per elaborare la risposta a mano., Ma più oggetti ci sono, più tassare questo calcolo diventa per una persona – o un computer.
Questo dilemma fittizio, il “problema dello zaino”, appartiene a una classe di problemi matematici famosi per spingere i limiti dell’informatica. E il problema dello zaino è più di un esperimento mentale. ” Molti problemi che affrontiamo nella vita, che si tratti di affari, finanza, compresa la logistica, carico di navi portacontainer, carico di aerei — questi sono tutti problemi a zaino”, afferma Carsten Murawski, professore all’Università di Melbourne in Australia., “Dal punto di vista pratico, il problema dello zaino è onnipresente nella vita di tutti i giorni.”
I ricercatori una volta hanno approfittato della complessità del problema per creare sistemi di sicurezza informatica, ma questi possono ora essere incrinati poiché il problema è stato così ben studiato. Oggi, come la tecnologia in grado di frantumare le serrature sulle nostre comunicazioni digitali si profilano all’orizzonte, il problema zaino può ispirare nuovi modi per prepararsi a quella rivoluzione.
Tutto o niente
Il problema dello zaino appartiene a una classe di problemi “NP”, che sta per “tempo polinomiale non deterministico.,”Il nome fa riferimento a come questi problemi costringono un computer a passare attraverso molti passaggi per arrivare a una soluzione, e il numero aumenta drasticamente in base alle dimensioni degli input, ad esempio l’inventario degli articoli tra cui scegliere quando si riempie un particolare zaino. Per definizione, i problemi NP hanno anche soluzioni facili da verificare (sarebbe banale verificare che un particolare elenco di elementi si adatti, in effetti, a uno zaino).,
“Il problema a cui i teorici hanno iniziato a guardare era l’efficienza con cui un particolare compito può essere svolto su un computer”, scrive Keith Devlin nel libro The Millennium Problems. Per esempio: Dato un elenco di 1 milione di manufatti del museo con i loro pesi e valori monetari, e uno zaino limitato a 25 sterline, un computer avrebbe dovuto correre attraverso ogni possibile combinazione per generare quello singolo con il bottino più redditizio. Data una quantità indefinita di tempo, un computer potrebbe usare la forza bruta per ottimizzare casi di grandi dimensioni come questo, ma non su scale temporali che sarebbero pratiche.,
“Pensiamo che si potrebbe coprire l’intera Terra con processori ed eseguirli fino alla morte di calore dell’universo e ancora non riescono a risolvere relativamente piccole istanze di versioni appropriate di questi problemi,” dice Noah Stephens-Davidowitz, un ricercatore Microsoft presso il Simons Institute di Berkeley, California.
Alcuni problemi NP come l’esempio dello zaino hanno una proprietà speciale: nei primi anni 1970, Stephen Cook e Richard Karp mostrarono che una varietà di problemi NP poteva essere convertita in un singolo problema di logica formale., Pertanto, se si potesse risolvere e verificare in modo efficiente con un algoritmo, tutti potrebbero. Questa proprietà è conosciuta come ” NP completezza.”
Una delle domande più ostinate in informatica e matematica è se questi problemi” NP”, incluso il problema dello zaino, siano veramente diversi dai problemi” P”, quelli che possono essere risolti in quello che viene chiamato tempo polinomiale. Se P = NP, allora è possibile risolvere ogni problema le cui soluzioni sono facili da verificare, dice Stephens-Davidowitz. Quindi, se questa disuguaglianza persiste, il problema generale dello zaino sarà sempre difficile.,
Mantenere le cose segrete
I ricercatori di crittografia amano i problemi che sono difficili da risolvere per i computer perché sono utili nella crittografia dei messaggi digitali. I codici di sicurezza simili a problemi non sono utili per questo, poiché sono troppo facilmente incrinati, ma sono in fase di sviluppo metodi più complicati ispirati a questo problema e potrebbero un giorno svolgere un ruolo nel superare in astuzia la prossima generazione di elaborazione.,
In un metodo di crittografia in stile zaino, la chiave privata di una persona sarebbe un elenco di numeri in cui ciascuno è più grande della somma dei suoi predecessori. Gli scambi che coinvolgono quella persona utilizzerebbero una chiave pubblica che sembra casuale ma è composta da numeri del primo elenco con trasformazioni specifiche applicate. Ad esempio, se la chiave pubblica è, il messaggio trasmesso “1, 0, 0, 1” verrà codificato come 2+0+0+5 = 7 (perché 2*1=2, 3*0=0, 4*0=0, e 5 * 1=5). I numeri segreti coinvolti nelle conversioni tra le chiavi consentono di svelare il messaggio originale.,
Affinché funzioni, un computer deve anche capire se un dato numero può essere scritto come la somma di un sottoinsieme di numeri nella chiave privata, che diventa un facile problema a zaino. È simile a riempire uno zaino con un lotto di oggetti di dimensioni diverse, come un anello, un dipinto, un’auto e una casa, e sapere che non puoi riempire nient’altro dopo aver controllato che l’anello e il dipinto si adattino. I crittografi Ralph Merkle e Martin Hellman hanno descritto questa idea nel 1978, ma altri hanno capito come decifrarla nei primi anni 1980.,
Gli scambi di informazioni private su Internet di oggi usano spesso chiavi che coinvolgono grandi numeri primi, e mentre il factoring di grandi numeri è difficile, non si pensa che appartenga alla stessa classe “NP complete” del problema dello zaino. Tuttavia, gli informatici si stanno già preparando per un futuro in cui i computer quantistici possono sbloccare rapidamente queste chiavi.
I computer quantistici si basano sui principi della meccanica quantistica, che dice che una particella non si trova in una singola posizione ma ha una probabilità di trovarsi in molti luoghi diversi a meno che non sia bloccata e misurata., Mentre i normali computer codificano le informazioni in 0 e 1, ogni “qubit” in un computer quantistico avrebbe una vasta gamma di possibili stati relativi alle proprietà delle particelle. I computer quantistici non sarebbero utili per navigare in Internet o scrivere una sceneggiatura in un bar, ma scatenerebbero un potere mai visto prima su alcuni tipi di problemi matematici. Sfortunatamente, questi problemi di matematica costituiscono le basi della moderna sicurezza informatica.
“In un certo senso, siamo stati davvero sfortunati”, dice Stephens-Davidowitz., “Siamo riusciti a riposare la sicurezza di Internet sulla durezza di alcuni dei pochissimi problemi che sembrano essere difficile per i computer classici, ma facile per i computer quantistici.”
Mentre l’informatica quantistica è nella sua infanzia, alcuni ricercatori dicono che siamo indietro nella preparazione per questo. Nel 2016, il National Institute of Standards and Technology (NIST) ha chiesto nuovi metodi di crittografia quantistica resistente, annunciando 26 semifinalisti l’anno scorso. Uno di questi tipi di algoritmo in fase di sviluppo è chiamato crittografia basata su reticolo., Invece di usare i numeri, utilizza chiavi che esistono in più dimensioni e implicano la formazione di una struttura reticolare fatta di punti equidistanti nello spazio. La domanda è dove sono quei punti e quanto è vicino un dato punto casuale alle coordinate di un reticolo. Nel suo cuore, questo è un problema di zaino in più di una dimensione.
“La mia attuale ossessione sta cercando di capire quanto siano sicure queste cose basate su reticolo, idealmente prima di usarle per eseguire Internet”, afferma Stephens-Davidowitz.,
“Ciò significa che abbiamo bisogno di crittografia quantistica resistente molto prima di quanto ci aspettiamo che i computer quantistici raggiungano il loro pieno potenziale”, ha affermato Leo Ducas, ricercatore presso il Centrum Wiskunde& Informatica nei Paesi Bassi.
Al di là della ricerca sulla crittografia, il problema dello zaino e i suoi cugini NP completi sono ovunque nella vita reale. Ad esempio, potresti aver sentito parlare del problema “commesso viaggiatore”, che è anche NP completo., La sfida qui è quella di trovare il percorso più breve per un venditore di viaggiare tra un dato numero di città prima di tornare al punto di partenza. Strettamente correlato è il problema di instradamento del veicolo, che considera più veicoli che effettuano consegne.
Luciana Buriol, professore associato presso l’Universidade Federal do Rio Grande do Sul in Brasile, ha attaccato questo problema per cercare di trovare nuovi approcci per il settore sanitario., Ha lavorato con un servizio di assistenza domiciliare in cui medici e infermieri visitano i pazienti nelle loro case e hanno contribuito a ottimizzare i loro percorsi, dato un numero limitato di auto disponibili per il trasporto.
“Dati 300 pazienti e 15 auto, non è possibile trovare la soluzione in un tempo ragionevole”, ha detto. “Se hai giorni per eseguire l’algoritmo troverai — ma devi trovare in meno di 2 ore, altrimenti non userai mai in pratica.”
Nessun singolo algoritmo one-size-fits-all può risolvere questi problemi., Invece, Buriol trova modi rapidi per arrivare a utili approssimazioni in modo che possano essere messe in azione.
Zaini intorno a noi
Per quelli di noi che non sono scienziati informatici e affrontano questo tipo di problemi nella vita reale, quanto siamo bravi? Il gruppo di Murawski trova risultati preliminari che quando si danno agli umani problemi simili a zaini, anche noi lottiamo potentemente., In piccoli esperimenti in cui ai partecipanti è stato chiesto di riempire uno zaino sullo schermo di un computer con oggetti che trasportano valori e pesi dichiarati, le persone tendevano ad avere più difficoltà a ottimizzare il contenuto dello zaino man mano che il numero di opzioni di oggetti aumentava, lo stesso problema dei computer. I ricercatori dicono che questa scoperta potrebbe essere correlata al “sovraccarico di scelta”: il modo in cui ci congeliamo quando vengono date troppe scelte, anche in situazioni semplici come l’acquisto di marmellata in un negozio di alimentari.
Eppure, nel mondo reale, ce la caviamo. Prestare attenzione è anche un problema di zaino., Durante la guida, ci troviamo di fronte a una cornucopia di possibili distrazioni come uccelli, nuvole, la radio, e gli edifici circostanti. Dobbiamo mettere solo gli stimoli più pertinenti nei nostri zaini mentali-e in generale, lo facciamo.
La domanda rimane: dato che i problemi NP completi sono più difficili per i computer rispetto ad altri tipi di enigmi, sono anche più difficili per le persone? I risultati iniziali limitati suggeriscono che potrebbero essere, che ha sorpreso Murawski.,
“Se questo risulta essere il caso, suggerirebbe che la durezza di tali problemi è una caratteristica dei problemi—una proprietà della natura—e non negli occhi di chi guarda”, dice Murawski.