La teoria della complessità è un insieme di classi di complessità – aggregati di problemi computazionali – che studia i sistemi complessi. Essa si è venuta affermando negli ultimi decenni grazie all’utilizzo di computer sempre più potenti e alla crescente inclinazione, nell’indagine scientifica, a rinunciare alle assunzioni di linearità nei sistemi dinamici, per indagarne più a fondo il comportamento reale.
Nella teoria della complessità, il termine MIP* rappresenta la classe di problemi che ammettono delle prove interattive con sperimentatori legati quantisticamente. Il termine RE (recursively enumerable) identifica invece l’insieme dei linguaggi enumerabili ricorsivamente, ovvero quei problemi che possono essere risolti con un computer.
In un recente articolo, gli scienziati Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen, hanno proposto uno studio per dimostrare la relazione MIP* = RE, che rappresenta una rilevante scoperta nel campo della teoria della complessità quantistica. Questa uguaglianza potrebbe rappresentare un dettaglio insignificante nell’ambito di una teoria astratta, senza alcuna applicazione nel mondo reale. Ma assume rilevante importanza per i fisici e i matematici, perché potrebbe implicare delle conseguenze sorprendenti nelle loro discipline.
Nel 1936, Alan Turing dimostrò che il Problema dell’arresto – ovvero decidere con un algoritmo se in un computer un programma si interrompe o avvia un processo di loop infinito – non può essere risolto. Poi è arrivata l’informatica moderna e si è avuta l’impressione che, grazie alla crescente potenza dei computer, molti problemi di natura pratica potessero risolversi.
Ma, ben presto, è apparso evidente che non tutti i problemi possono essere risolti con specifici algoritmi. Capire solo come risolvere i problemi non è più sufficiente, in quanto si richiede una determinata classificazione delle soluzioni in termini di efficienza. La teoria della complessità classifica i problemi sulla base del tempo computazionale impiegato per risolverli.
Diamo uno sguardo ad altre sottoclassi di problemi.
La classe P include l’insieme di problemi che possono essere risolti velocemente da un algoritmo noto (tecnicamente, in un tempo polinomiale). Per esempio, il prodotto tra due numeri appartiene alla classe di problemi P, in quanto la moltiplicazione lunga è un algoritmo efficiente per risolvere il problema. Si sa, inoltre, che il problema della determinazione dei fattori primi di un numero non appartiene alla classe P; il problema può sicuramente essere risolto da un computer, ma non esiste alcun algoritmo che può risolvere tale problema efficientemente. Un problema legato a quest’ultimo, è decidere se un dato numero rappresenta un numero primo; nel 2004, è stato finalmente trovato un algoritmo efficiente, che ha permesso di inserire questo problema nella classe P.
Un’altra classe di complessità è data da NP. Si immagini un labirinto. La domanda “esiste una via d’uscita dal labirinto?” presuppone una risposta di tipo SI/NO. Se la risposta è SI, allora c’è un modo semplice per convincerci: si acquisiscono le direzioni, si seguono queste direzioni e si troverà l’uscita. Se invece la risposta è NO, per convincerci, avremmo dovuto attraversare l’intero labirinto senza mai trovare la via d’uscita.
Questo tipo di problemi SI/NO, per i quali, se la risposta è SI, essa può essere dimostrata efficientemente, appartengono alla categoria NP. Qualunque soluzione di un problema è utile per convincerci della risposta, e quindi la classe P è contenuta nella classe NP.
Le classi sopra descritte rappresentano dei problemi che possono essere analizzati e studiati con un computer normale. Con il tempo l’informatica è andata progredendo e si sono sviluppati i computer quantistici. Ma se un un nuovo tipo di computer si propone come capace di risolvere i nostri problemi, quali elementi abbiamo per fidarci dell’esattezza dei calcoli da esso compiuti?
Si immagini l’interazione tra due entità, per esempio, in una stazione di polizia, un investigatore e un sospettato, che deve provare la sua innocenza. L’investigatore deve decidere se il sospettato è sufficientemente convincente. Ma tra i due vi è uno squilibrio; dal punto di vista della conoscenza, l’investigatore si trova in una posizione di inferiorità rispetto al sospettato.
Nella teoria della complessità, l’investigatore è la persona, con un potere computazionale limitato, che cerca di risolvere il problema. Il sospettato rappresenta il nuovo computer, a cui si attribuisce una grande capacità computazionale. Un sistema di prova interattivo è un protocollo che un investigatore può utilizzare allo scopo di determinare, con la più alta probabilità concessa, se il sospettato può essere ritenuto credibile. Per analogia, questi sono esempi di crimini che la polizia potrebbe anche non riuscire a risolvere, ma per i quali, alla fine, gli innocenti hanno la possibilità di dimostrare la loro innocenza. Questa è la categoria dei problemi IP.
Se vengono interrogati più sospettati, e gli stessi non possono coordinare le loro risposte (il caso in cui la polizia interroga più persone sospette), allora ci si trova nella classe di problemi MIP. Questo tipo di interrogatori, attraverso l’analisi incrociata delle risposte degli interrogati, pone l’investigatore in una posizione di privilegio; per questo la classe MIP contiene la classe IP.
La comunicazione quantistica è una nuova forma di comunicazione trasportata dai qubit. L’entanglement – il fenomeno per il quale i qubit rimangono legati anche se fisicamente separati – rende la comunicazione quantistica fondamentalmente differente dalla comunicazione ordinaria. Consentire agli interrogati della MIP di condividere un qubit legato conduce ai problemi di classe MIP*.
Sembra ovvio che la comunicazione tra due interrogati serve solo a coordinare le loro risposte, piuttosto che agevolare l’investigatore nella ricerca della verità. Per questa ragione, nessuno si aspettava che la condivisione di una maggiore comunicazione avrebbe reso i problemi più facili da risolvere. Invece, con sorpresa, si è dimostrato che MPI* = RE, ovvero che la comunicazione quantistica si comporta in modo completamente diverso dalla comunicazione normale.
Negli anni Settanta, Alain Connes formulò quella che sarebbe diventata la congettura di Connes (Connnes Embedding Problem). In poche parole, il problema chiedeva se delle matrici infinite potessero essere approssimate da matrici finite. Il lavoro, oggetto di questo articolo, ha provato che ciò non è possibile; un risultato che rappresenta una scoperta importante per i matematici.
Intanto, nel 1993, Boris Tsirelson propone un problema fisico noto come Problema di Tsirelson. Questo problema riguarda la possibilità di esprimere con due formalismi matematici diversi la medesima situazione in meccanica quantistica – una teoria che riscuote ampio successo per la spiegazione del mondo subatomico. Trattandosi della descrizione dello stesso fenomeno attraverso due diversi formalismi, ci si aspettava che i formalismi fossero matematicamente equivalenti.
Ma il nuovo studio ha dimostrato che non è così. Non è noto esattamente come entrambi i formalismi possano dare gli stessi risultati e descrivere la stessa realtà fisica; ma proprio questa carenza di conoscenza induce i fisici ad approfondire maggiormente l’argomento.
Il tempo dirà quali altre domande scientifiche senza risposta saranno fornite dallo studio della complessità. Una cosa è certa: che la relazione MIP* = RE rappresenta un grande passo avanti.
Fonte: The conversation
