La teoria della complessità: la sorpresa del secolo?

Spektrum der Wissenschaft

4.3.2020

Traduzione: tradotto automaticamente

È una delle grandi domande dell'informatica: i computer possono risolvere qualsiasi problema in un tempo ragionevole? Sì, dice un nuovo documento tecnico che sta suscitando molto entusiasmo.

Gli scienziati amano categorizzare le cose, almeno a livello astratto. I chimici, ad esempio, classificano tutti gli elementi nella tavola periodica. I biologi classificano gli esseri viventi della Terra in famiglie e specie. E i matematici, dopo una lunga ricerca, hanno trovato ed elencato tutti i gruppi semplici infiniti nell'ultimo decennio.

Anche gli scienziati informatici cercano l'ordine, anche se in modo un po' diverso: ordinano i problemi in base alla loro complessità. In passato hanno già scoperto che alcuni compiti sono molto facili da risolvere per i computer. Il tempo di calcolo necessario per risolverli aumenta lentamente (in modo polinomiale) con la lunghezza del problema. Dal punto di vista degli informatici, questi compiti di calcolo appartengono quindi alla classe di complessità P.

I problemi facili da verificare, anche se difficili da risolvere, appartengono alla classe NP. Un esempio è un difficile rompicapo di Sudoku: è difficile trovare la soluzione corretta. Tuttavia, una volta che l'hai risolta o che ti è stato presentato un foglio completato, è facile verificare se è corretta.

Il divertimento inizia con P e NP: gli informatici hanno creato una gerarchia di classi di complessità, da molto semplici a estremamente sofisticate. Il computer quantistico ha portato una svolta: consente nuove strategie quando si tratta di verificare la correttezza della soluzione data a un problema.

Una questione aperta nella ricerca sulla complessità è sempre stata quella di stabilire quanto possa essere complicato un problema al massimo affinché un computer possa comunque risolverlo in un tempo ragionevole, cioè polinomiale. Un team guidato da Zhengfeng Ji della University of Technology di Sydney ha ora trovato una risposta sorprendente che sta facendo scalpore tra gli esperti. Secondo la teoria, anche i problemi più difficili dell'informatica possono essere affrontati in un tempo ragionevole.

"Non riesco a pensare a una sola persona che se lo sarebbe aspettato", scrive lo stimato informatico Scott Aaronson dell'Università di Austin nel suo blog. Se il lavoro dovesse reggere all'esame di esperti indipendenti, sarebbe una delle più grandi sorprese dell'informatica teorica di questo secolo.

La lunga storia delle classi di complessità

Dagli anni '70, gli informatici hanno cercato di suddividere le classi di complessità in modo sempre più preciso. A tal fine, hanno ripetutamente identificato i problemi più complicati come NP. L'obiettivo principale di una maggiore complessità era la verifica della soluzione. In alcuni casi, il tempo necessario per farlo non aumenta più in modo polinomiale con la lunghezza del compito, ma piuttosto in modo esponenziale. Questo rende le cose molto più difficili rispetto a un puzzle di Sudoku, la cui soluzione viene presentata all'utente.

Per poter classificare tali problemi, negli anni '80 gli informatici hanno introdotto i cosiddetti sistemi di dimostrazione interattiva. Hanno immaginato un computer onnipotente, il "prover". Questo computer è sempre in grado di fornire la soluzione a un problema, indipendentemente dalla sua complessità. Può quindi calcolare anche problemi molto più complicati del Sudoku. Ha una capacità di memoria infinita e, in linea di principio, può calcolare per un tempo infinito.
Tuttavia, il prover è in grado di fornire sempre la soluzione del problema, indipendentemente dalla sua complessità.
Tuttavia, il prover non è affidabile, per questo motivo è necessario un verificatore che ricalcoli il risultato fornito. Nel Sudoku, è il verificatore a garantire che la soluzione sia corretta. A differenza del prover, il verificatore è un computer realistico che dispone di risorse limitate. Questo significa che il suo tempo di calcolo può dipendere solo in modo polinomiale dalla dimensione del compito.

Poiché la soluzione fornita dal prover può essere estremamente lunga e complicata, l'esaminatore pone diverse domande al prover nel tentativo di accertarne la veridicità. Si consideri, ad esempio, un tavolo in una stanza buia come la pece su cui giacciono diversi blocchi di legno di forma identica. Il compito è quello di ordinarli in base al loro colore. Il dimostratore, onnipotente, non ha alcun problema. Nonostante l'oscurità, divide i blocchi in due mucchi.

L'esaminatore deve ora porre delle domande per scoprire se due blocchi scelti a caso da due pile diverse sono davvero di colori diversi. In questo caso, l'esaminatore potrebbe dire che un blocco è rosso e l'altro è blu. Ma è vero? Oppure il dimostratore sta mentendo? Per scoprirlo, l'esaminatore può nascondere i blocchi di legno dietro la schiena, scambiarli e chiedere al dimostratore quale sia quello rosso. Se l'esperimento viene ripetuto abbastanza spesso, la persona che fornisce la prova si sbaglierà in circa la metà dei casi se ha mentito, oppure risponderà sempre correttamente, a patto che abbia detto la verità.

Interrogatorio di più sospetti

Gli scienziati informatici hanno scoperto che la soluzione di alcuni compiti può essere verificata solo utilizzando questa strategia di interrogazione. Se si prendono in considerazione questi problemi, la classe di complessità NP si espande a "IP". Esiste anche un modo per affrontare problemi ancora più complessi: Consentire non un solo ragionatore, ma più di uno. Possono scambiarsi informazioni mentre lavorano a un compito. Tuttavia, non appena consegnano un risultato e l'esaminatore lo analizza, si separano l'uno dall'altro.
In questo modo, il ragionatore è in grado di risolvere il problema.
In questo modo, il compito che l'esaminatore affronta utilizzando la strategia domanda-risposta può essere ancora più complicato e comunque verificato in tempo polinomiale. Questo perché per l'esaminatore è più facile interrogare due o più istanze: Proprio come un ispettore di polizia ha maggiori possibilità di condannare i testimoni che mentono se ha diversi interrogatori separati, anche i problemi più impegnativi possono essere risolti in questo modo. La classe di complessità associata "MIP" è addirittura superiore a quella di IP, come gli informatici scoprirono nel 1988.

Dopo questo risultato, gli scienziati hanno scoperto che il problema è più complesso di quello di IP.

Dopo questo risultato, il campo dei sistemi di prova interattivi si è fermato. Almeno fino a quando alcuni ricercatori si sono chiesti cosa sarebbe successo se i due dimostratori non fossero stati computer classici, ma computer quantistici accoppiati tra loro tramite la fisica quantistica. Questo è possibile grazie al fenomeno dell'entanglement, su cui Albert Einstein si era già scervellato.

L'autore lo chiamò "entanglement".

Lo chiamò "azione spettrale a distanza", perché se si misura lo stato di uno dei due oggetti entangled, si determina anche lo stato dell'altro, indipendentemente dalla distanza. Inizialmente questo fatto fece venire il mal di pancia ai fisici, ma ora si sa che nessuna informazione può essere trasportata in questo modo.
All'inizio, la complessità ha avuto un ruolo fondamentale nel trasporto di informazioni.
All'inizio, i ricercatori della complessità non hanno prestato molta attenzione alla possibilità di avere dei provers entangled, in quanto si presumeva che la classe di complessità associata MIP* sarebbe stata più piccola di MIP o addirittura di IP. Dopo tutto, il vantaggio di MIP è che i computer onniscienti vengono interrogati separatamente. Se, invece, sono entangled, la risposta di uno influenza lo stato dell'altro.

"La reazione naturale di tutti, me compreso, è stata quella di dare più potere ai provers", ha ricordato l'informatico Thomas Vidick del California Institute of Technology, co-autore della nuova pubblicazione, qualche tempo fa su Quanta Magazine. Dopo tutto, i responsabili delle prove potrebbero usare l'entanglement per coordinare le loro risposte durante l'interrogatorio da parte dell'esaminatore.

I computer quantistici entangled come soluzione

La prima grande sorpresa è arrivata però nel 2012: Vidick ha dimostrato con il suo collega Tsuyoshi Ito dell'Università di Waterloo che i computer quantistici entangled possono essere utilizzati anche per verificare tutti i problemi di MIP in tempo polinomiale. Ciò significa che entrambe le classi di complessità sono almeno della stessa dimensione.

Il prossimo colpo di scena è avvenuto nel 2019. I fisici Anand Natarajan del California Institute of Technology e John Wright del Massachusetts Institute of Technology hanno scoperto che la classe di computer quantistici MIP* è ancora più grande di MIP. Questo significa che l'entanglement non deve essere necessariamente uno svantaggio, ma anzi l'esaminatore può usarlo a proprio vantaggio - e quindi effettuare controlli incrociati anche su compiti più complessi del previsto.

Il trucco è individuare i compiti più complessi da svolgere.

Il trucco consiste nell'identificare le domande adatte attraverso l'interleaving. In altre parole, i fornitori di prove interrogano per primi se stessi. A prima vista può sembrare paradossale, ma poiché i due fornitori di prove sono collegati tra loro, possono esaminare più risposte contemporaneamente e quindi affrontare più fasi di verifica possibili. Queste domande vengono trasmesse all'esaminatore.
L'esaminatore si limita quindi a verificare le risposte.
L'esaminatore deve solo garantire che le domande siano rappresentative e significative e che le risposte non portino a contraddizioni durante la prova vera e propria. In questo modo, può svolgere il test in un tempo ragionevole; il tempo di calcolo richiesto aumenta semplicemente in modo polinomiale con la lunghezza del test.

Questa strategia di "domande correlate" consente di verificare una prova più rapidamente. Tuttavia, bisogna fare attenzione che le risposte fornite dai prover non siano anch'esse intrecciate. Ciò equivarrebbe a due sospetti che colludono durante un interrogatorio. Natarajan e Wright hanno risolto il problema utilizzando un altro bizzarro concetto della meccanica quantistica: l'incertezza intrinseca del microcosmo, secondo la quale due proprietà "complementari" di un oggetto, come la posizione e la quantità di moto, non possono essere determinate con precisione arbitraria allo stesso tempo.

Se hai misurato la posizione e la quantità di moto, non puoi fare a meno di farlo.

Se hai misurato la velocità di una particella e poi hai determinato la sua posizione, non sai più a che velocità si trova ora l'oggetto. Per questo motivo, i due dimostratori possono effettuare solo misurazioni complementari in modo che le loro risposte non si influenzino a vicenda. Se chiedi al primo computer quantistico un valore calcolato, questo cancella le informazioni corrispondenti dal secondo computer quantistico.

Ora gli informatici sapevano che MIP* supera la complessità di MIP. Tuttavia, inizialmente non era chiaro quanto fosse ampia la classe. Quanto è possibile verificare le soluzioni chiedendo ai computer quantistici entangled? In effetti, questo sembra massimizzare il numero di compiti: Come hanno dimostrato Zhengfeng Ji insieme a Natarajan, Vidick, Wright e Henry Yuen dell'Università di Toronto nel loro sensazionale tecnico, il MIP* contiene tutti i problemi computabili dell'informatica.

Secondo la prova, MIP* è identico alla classe di complessità enorme RE. Include tutti i problemi decisionali (quelli la cui risposta è sì o no) a cui un computer può rispondere affermativamente in un tempo finito. Questo include, tra le altre cose, il famoso problema di halting: Si tratta di determinare se un computer si fermerà mai durante il calcolo di un compito - o se continuerà a calcolare per sempre.

L'informatico britannico Alan Turing ha dimostrato nel 1936 che non esiste un algoritmo in grado di risolvere il problema di halting in generale. Tuttavia, ciò non contraddice l'ultima pubblicazione. Infatti, il lavoro di Ji e dei suoi colleghi afferma che un verificatore ordinario può controllare in tempo polinomiale l'affermazione di due computer quantistici onniscienti entangled che affermano che un computer si arresterà per un determinato compito.

Un colpo di scena inaspettato per i matematici

Questo è già di per sé notevole. Ma il risultato degli informatici ha anche implicazioni per la matematica e la fisica quantistica. Infatti, si scopre che il problema dell'incorporazione formulato dal vincitore della Medaglia FieldsAlain Connes negli anni '70 era sbagliato - cosa che molti scienziati non si aspettavano. Da questo dipendono altre ipotesi, che di conseguenza non possono essere corrette.

Il problema dell'incorporazione riguarda, tra l'altro, le cosiddette algebre di operatori, che appartengono al campo matematico dell'analisi funzionale, ma compaiono anche nella meccanica quantistica. Esiste infatti un'affermazione fisica equivalente al problema di Connes: tutte le correlazioni consentite dalla meccanica quantistica possono essere approssimate arbitrariamente bene da un numero finito di qubit entangled. Contrariamente a quanto la maggior parte degli scienziati si aspettava, il risultato degli informatici teorici dimostra che questa affermazione è falsa.

Questo ha conseguenze drastiche, ad esempio per quanto riguarda la differenza tra sistemi finiti e infiniti. Contrariamente a quanto spesso si pensa, un sistema infinito non può sempre essere approssimato con precisione da uno finito. Nella loro pubblicazione, Ji e i suoi colleghi fanno un esempio di una situazione in cui due persone stanno giocando una partita. Se entrambi sono infinitamente entangled l'uno con l'altro, allora vincono con una probabilità pari a uno; se invece sono solo finitamente entangled, allora la probabilità è al massimo di uno e mezzo.

Tuttavia, a differenza delle inequalities formulate da John Bell negli anni '60, questo gioco non può essere testato in laboratorio, poiché non esiste un modo per agganciare due sistemi all'infinito l'uno con l'altro. Tuttavia, il lavoro dimostra che la teoria della complessità - contrariamente a quanto spesso si sostiene - non è un campo completamente distante che sta in piedi da solo, ma ha un impatto su altri settori, anche se astratti come la fisica quantistica teorica.

Spettro della scienza

Siamo partner di Spektrum der Wissenschaft e vogliamo rendere più accessibili a te informazioni fondate. Segui Spektrum der Wissenschaft se ti piacciono gli articoli.

[[small:]]

Spektrum der Wissenschaft

Wissenschaft aus erster Hand

dirdjaja@spektrum.de

Gli esperti della scienza e della ricerca riferiscono sulle ultime scoperte nei loro campi – competenti, autentiche e comprensibili.

Segui

---

Informatica

Segui gli argomenti e ricevi gli aggiornamenti settimanali relativi ai tuoi interessi.

Segui argomento

Potrebbero interessarti anche questi articoli