Un problema apparentemente semplice produce numeri troppo grandi per il nostro universo | Rivista Quanti

Non capita spesso che i bambini di 5 anni riescano a cogliere le domande sulle frontiere dell'informatica, ma può succedere. Supponiamo, ad esempio, che una bambina dell'asilo di nome Alice abbia due mele, ma preferisce le arance. Fortunatamente, i suoi compagni di classe hanno sviluppato un sano sistema di commercio della frutta con tassi di cambio rigorosamente applicati: rinuncia a una mela, ad esempio, e puoi ottenere una banana. Riuscirà Alice a eseguire una serie di operazioni, raccogliendo e scaricando banane o meloni, che la condurranno al suo frutto preferito?

Sembra abbastanza semplice. “Puoi andare alla scuola elementare e raccontarlo ai bambini”, ha detto Christoph Haase, uno scienziato informatico presso l'Università di Oxford. "La gente penserà: 'Deve essere facile.'"

Ma il problema matematico alla base del dilemma di Alice – chiamato problema di raggiungibilità per i sistemi di addizione vettoriale – è sorprendentemente sottile. Sebbene alcuni casi possano essere risolti facilmente, gli informatici hanno lottato per quasi mezzo secolo per sviluppare una comprensione completa del problema. Ora, in una serie di scoperte negli ultimi anni, hanno stabilito con fermezza quanto può diventare complesso quel problema.

Si scopre che questo problema infantile è assurdamente, quasi come un cartone animato, così complesso come praticamente tutti gli altri problemi computazionali notoriamente difficili sembra, beh, un gioco da ragazzi. Prova a quantificare lo sforzo richiesto per risolvere questo problema e presto ti troverai di fronte a numeri così grandi che anche contarne le cifre ti porterà a raggiungere numeri di cui non hai mai sentito parlare. Tali numeri spesso invitano a fare paragoni con la scala dell’universo, ma anche queste analogie non sono sufficienti. "Ciò non gli renderebbe giustizia", ​​ha detto Georg Zetzsche, scienziato informatico presso l'Istituto Max Planck per i sistemi software di Kaiserslautern, in Germania. “L’universo è così piccolo.”

A portata di mano?

Spogliato alla sua essenza, il problema della raggiungibilità riguarda oggetti matematici chiamati vettori, che sono elenchi ordinati di numeri. Le voci in questi elenchi sono chiamate componenti e il numero di componenti di un vettore è chiamato dimensionalità. L'inventario della frutta di Alice, ad esempio, può essere descritto da un vettore quadridimensionale (a, b, c, d), i cui componenti rappresentano quante mele, banane, meloni e arance ha in un dato momento.

Un sistema di addizione vettoriale, o VAS, è una raccolta di vettori che rappresentano le possibili transizioni tra gli stati in un sistema. Per Alice, il vettore di transizione (−1, −1, 1, 0) rappresenterebbe lo scambio di una mela e una banana con un melone. Il problema della raggiungibilità VAS chiede se esiste una combinazione di transizioni consentite che può portarti da uno specifico stato iniziale a uno specifico stato di destinazione o, in termini matematici, se esiste una somma di vettori di transizione che trasforma il vettore di partenza nel vettore di destinazione. C'è solo un problema: nessuna componente del vettore che descrive lo stato del sistema potrà mai scendere sotto lo zero.

"Questa è una restrizione molto naturale per un modello di realtà", ha detto Wojciech Czerwiński, informatico dell'Università di Varsavia. "Non puoi avere un numero di mele negativo."

In alcuni sistemi è facile determinare se il vettore target è raggiungibile. Ma non è sempre così. Gli informatici sono più interessati ai sistemi di addizione vettoriale dall'aspetto semplice in cui non è ovvio quanto sia difficile determinare la raggiungibilità. Per studiare questi casi, i ricercatori iniziano definendo un numero che quantifica la dimensione di un dato sistema. Questo numero, rappresentato da n, comprende il numero di dimensioni, il numero di transizioni e altri fattori. Poi si chiedono quanto velocemente può aumentare la difficoltà del problema di raggiungibilità n diventa più grande.

Per rispondere a questa domanda, i ricercatori utilizzano due approcci complementari. Innanzitutto, cercano esempi di sistemi di addizione vettoriale particolarmente complicati in cui determinare la raggiungibilità richiede un livello minimo di sforzo. Questi livelli minimi sono chiamati “limiti inferiori” sulla complessità del problema – dicono ai ricercatori: “I sistemi più complicati per un dato n sono almeno così difficili.

In secondo luogo, i ricercatori cercano di stabilire “limiti superiori” – limiti su quanto difficile possa diventare la raggiungibilità, anche nei sistemi più diabolici. Questi dicono: “I casi più complicati per un dato n sono al massimo così difficili. Per determinare con precisione quanto sia difficile la raggiungibilità nei sistemi più complicati, i ricercatori provano a spingere i limiti inferiori verso l’alto e quelli superiori verso il basso finché non si incontrano.

La roba degli incubi

I sistemi di addizione vettoriale hanno una lunga storia. Sin dagli anni '1960, gli informatici li hanno utilizzati per modellare programmi che suddividono un calcolo in tante piccole parti e lavorano su quelle parti simultaneamente. Questo tipo di “calcolo simultaneo” è ormai onnipresente, ma i ricercatori non ne comprendono ancora appieno i fondamenti matematici.

Nel 1976, l'informatico Riccardo Lipton ha compiuto il primo passo verso la comprensione della complessità del problema della raggiungibilità VAS. Ha sviluppato una procedura per costruire sistemi in cui il modo più veloce per determinare se uno stato è raggiungibile da un altro è tracciare una sequenza di transizioni tra di loro. Ciò gli ha permesso di utilizzare la lunghezza del percorso più breve tra due stati scelti con cura come misura della difficoltà del problema della raggiungibilità.

Lipton allora dimostrato potrebbe costruire un sistema di dimensioni n in cui il percorso più breve tra due stati coinvolge più di transizioni $latex 2^{2^n}$. Ciò implicava un corrispondente doppio limite inferiore esponenziale sullo sforzo richiesto per determinare la raggiungibilità nei suoi sistemi. È stata una scoperta sorprendente: la doppia crescita esponenziale è l'oggetto degli incubi degli informatici. In effetti, i ricercatori spesso si oppongono anche alla crescita esponenziale ordinaria, che impallidisce al confronto: $latex {2^5}= 32$, ma $latex 2^{2^5}$ supera i 4 miliardi.

La maggior parte dei ricercatori pensava che Lipton avesse escogitato il sistema di addizione di vettori più complesso possibile, il che significa che aveva alzato il limite inferiore il più in alto possibile. L’unica cosa che manca, in quel caso, sarebbe un limite superiore, vale a dire la prova che non può esistere un sistema in cui determinare la raggiungibilità sia ancora più difficile. Ma nessuno sapeva come dimostrarlo. L'informatico Ernst Mayr si è avvicinato di più quando lui dimostrato nel 1981 che è sempre possibile, in linea di principio, determinare la raggiungibilità in qualsiasi sistema di addizione vettoriale. Ma la sua dimostrazione non ha posto alcun limite quantitativo superiore alla complessità del problema. C'era un pavimento, ma nessun soffitto in vista.

"Certamente ci ho pensato di tanto in tanto", ha detto Lipton. "Ma dopo un po' ho rinunciato e, per quanto ne so, per circa 40 anni nessuno ha fatto alcun progresso."

Nel 2015, gli informatici Jerome Leroux ed Sylvain Schmitz finalmente stabilito un limite superiore quantitativo – uno così alto che i ricercatori hanno pensato che fosse solo un primo passo che avrebbe potuto essere spinto verso il basso per raggiungere il limite inferiore di Lipton.

Ma non è quello che è successo. Nel 2019, i ricercatori hanno scoperto un limite inferiore molto più alto di quello di Lipton, ribaltando decenni di saggezza convenzionale. Il problema della raggiungibilità del VAS era molto più complesso di quanto chiunque avesse previsto.

Una torre di poteri

Lo scioccante risultato del 2019 è il risultato di un fallimento. Nel 2018 Czerwiński ha smentito una congettura di Leroux e Filippo Mazowiecki, scienziato informatico ora presso l'Università di Varsavia, che avrebbe contribuito a fare progressi su un problema correlato. Nelle discussioni successive, i ricercatori hanno trovato un nuovo modo promettente per costruire sistemi di addizione di vettori extra-complessi, che potrebbe implicare un nuovo limite inferiore al problema della raggiungibilità VAS, dove i progressi erano rimasti in fase di stallo per così tanto tempo.

“Tutto nella mia mente era legato alla raggiungibilità del VAS”, ricorda Czerwiński. Durante un semestre con un carico didattico leggero, decise di concentrarsi esclusivamente su quel problema, insieme a Leroux, Mazowiecki e altri due ricercatori — Slawomir Lasota dell'Università di Varsavia e Ranko Lazić dell'Università di Warwick.

Dopo alcuni mesi, i loro sforzi furono ripagati. Czerwiński e i suoi colleghi dimostrato che potevano costruire sistemi di addizione vettoriale in cui il percorso più breve tra due stati era correlato alla dimensione del sistema mediante un'operazione matematica chiamata tetrazione che fa sembrare docile anche l'incubo della doppia crescita esponenziale.

La tetrazione è una semplice estensione di uno schema che collega le operazioni più familiari in matematica, a cominciare dall'addizione. Sommare insieme n copie di un numero e il risultato equivale a moltiplicare quel numero per n. Se moltiplichi insieme n copie di un numero, equivale all'esponenziazione o all'elevamento del numero a nth potere. La tetrazione, spesso rappresentata da una coppia di frecce rivolte verso l'alto, è il passo successivo in questa sequenza: Tetrare un numero per n significa elevarlo n volte per produrre una torre di poteri n storie alte.

È difficile capire quanto velocemente la tetrazione sfugge di mano: $latex 2 uparrowuparrow 3$, o $latex 2^{2^2}$, è 16, $latex 2 uparrowuparrow 4$ è poco più di 65,000 e $latex 2 uparrowuparrow 5$ è un numero con quasi 20,000 cifre. È fisicamente impossibile scrivere tutte le cifre di $latex 2 uparrowuparrow 6$: uno svantaggio di vivere in un universo così piccolo.

Nel loro risultato fondamentale, Czerwiński e i suoi colleghi hanno dimostrato che esistono sistemi di addizione vettoriale di dimensioni n dove il modo migliore per determinare la raggiungibilità è tracciare un percorso che coinvolga più di transizioni $latex 2 uparrowuparrow n$, implicando un nuovo limite inferiore che fa impallidire quello di Lipton. Ma per quanto la tetrazione possa far girare la testa, non era ancora l’ultima parola sulla complessità del problema.

A Quinquagintillion e oltre 

Solo pochi mesi dopo il nuovo scioccante limite inferiore sulla complessità della raggiungibilità VAS, Leroux e Schmitz spinto giù il limite superiore che avevano stabilito tre anni prima, ma non arrivarono fino alla tetrazione. Invece, hanno dimostrato che la complessità del problema della raggiungibilità non può crescere più velocemente di una mostruosità matematica chiamata funzione di Ackermann.

Per comprendere questa funzione, prendiamo il modello utilizzato per definire la tetrazione fino alla sua triste conclusione. L'operazione successiva nella sequenza, chiamata pentazione, rappresenta la tetrazione ripetuta; è seguita ancora da un'altra operazione (esazione) di penitenza ripetuta, e così via.

La funzione di Ackermann, denominata $latex A(n)$, è ciò che ottieni quando sali di un gradino in questa scala di operazioni con ogni arresto sulla linea numerica: $latex A(1) = 1 + 1$, $latex A (2) = 2 × 2$, $latex A(3) = 3^3$, $latex A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$ e così via. Il numero di cifre in $latex A(4)$ è esso stesso un numero colossale pari approssimativamente a 1 quinquagintillion: questo è il nome bizzarro e raramente necessario per un 1 seguito da 153 zeri. "Non preoccuparti per Ackermann di 5", consiglia Javier Esparza, informatico presso l'Università Tecnica di Monaco.

Il risultato di Leroux e Schmitz ha lasciato un ampio divario tra i limiti inferiore e superiore: la complessità precisa del problema di raggiungibilità VAS potrebbe trovarsi alle estremità dell'intervallo o in qualsiasi punto intermedio. Czerwiński non intendeva lasciare che questa lacuna restasse. "Abbiamo continuato a lavorarci perché era chiaro che fosse la cosa più grande che avessimo mai fatto nella nostra vita", ha detto.

La svolta finale è arrivata nel 2021, mentre Czerwiński forniva consulenza a uno studente universitario del secondo anno di nome Łukasz Orlikowski. Assegnò a Orlikowski una semplice variante del problema per tenerlo aggiornato, e il lavoro di Orlikowski aiutò i due a sviluppare una nuova tecnica che si applicava anche al problema generale della raggiungibilità. Ciò glielo ha permesso alzare il limite inferiore sostanzialmente – fino al limite superiore di Ackermann di Leroux e Schmitz. Lavorando in modo indipendente, Leroux ottenne un risultato equivalente nello stesso momento.

Alla fine, i ricercatori hanno individuato la reale complessità del problema della raggiungibilità. Il limite inferiore di Czerwiński, Orlikowski e Leroux ha mostrato che esiste una sequenza di sistemi di addizione vettoriale progressivamente più grandi in cui il percorso più breve tra due stati cresce in proporzione alla funzione di Ackermann. Il limite superiore di Leroux e Schmitz ha dimostrato che il problema della raggiungibilità non può essere più complesso di così: poca consolazione per chiunque speri in una procedura pratica infallibile per risolverlo. È un esempio lampante di quanto possano essere sottili problemi computazionali apparentemente semplici.

Mai finito

I ricercatori hanno continuato a studiare il problema della raggiungibilità VAS dopo averne determinato l'esatta complessità, poiché molte varianti della domanda rimangono senza risposta. I limiti superiore e inferiore di Ackermann, ad esempio, non fanno distinzione tra i diversi modi di aumento n, come aumentare la dimensionalità dei vettori o aumentare il numero di transizioni consentite.

Recentemente Czerwiński e i suoi colleghi lo hanno fatto fatto progressi separando questi effetti distinti studiando la rapidità con cui la complessità può aumentare nelle varianti dei sistemi di addizione vettoriale con dimensionalità fissa. Ma resta ancora molto da fare: anche in tre dimensioni, dove i sistemi di addizione vettoriale sono facili da visualizzare, l’esatta complessità del problema della raggiungibilità rimane sconosciuta.

"In un certo senso, è semplicemente imbarazzante per noi", ha detto Mazowiecki.

I ricercatori sperano che una migliore comprensione di casi relativamente semplici li aiuterà a sviluppare nuovi strumenti per studiare altri modelli di calcolo più elaborati dei sistemi di addizione vettoriale. Attualmente non sappiamo quasi nulla di questi modelli più elaborati.

"Lo considero parte di una ricerca fondamentale per comprendere la computabilità", ha affermato Zetzsche.

Quanta sta conducendo una serie di sondaggi per servire meglio il nostro pubblico. Prendi il nostro Sondaggio tra i lettori di informatica e potrai partecipare alla vincita gratuita Quanta merce.