Scienziati informatici sempre più vicini al principale obiettivo algoritmico | Rivista Quanta

Se qualcuno ti chiede di determinare se due oggetti sono uguali, potrebbe sembrare una richiesta banale. Nella maggior parte dei casi quotidiani, basta una rapida occhiata per esprimere un giudizio accurato.

Ma nell'informatica, è una questione molto più complicata. In effetti, è uno che taglia al cuore irrisolto di ciò di cui sono capaci i computer. A seconda di quali sono gli oggetti e di come definisci l'uguaglianza, non sappiamo ancora se i computer possono rispondere rapidamente alla domanda o se un approccio lento e laborioso è essenzialmente il meglio che possono gestire.

Nell'ultimo decennio, ci sono stati alcuni importanti risultati che dimostrano che i computer possono fare almeno un po' meglio di così. Uno di maggiori risultati recenti in informatica era un algoritmo più veloce per determinare quando due grafici sono uguali. Il lavoro del 2015, di László Babai dell'Università di Chicago, ha infranto un'importante barriera di velocità computazionale ma non è riuscita a superarne un'altra.

Ora, un documento di Xiaorui Sole dell'Università dell'Illinois, Chicago, ha presentato un nuovo e più veloce algoritmo per una questione correlata chiamata problema dell'isomorfismo di gruppo, che consiste nel sapere quando due oggetti matematici chiamati gruppi sono uguali. Il lavoro, pubblicato online lo scorso marzo, fa un piccolo passo verso il chiarimento della complessità computazionale sottostante coinvolta nel confronto tra oggetti.

Il lavoro di Sun infrange un limite di velocità di vecchia data per una particolare classe di gruppi, quella considerata l'istanza più difficile da risolvere del problema dell'isomorfismo di gruppo. Se un algoritmo può confrontare rapidamente gruppi di questo tipo, la speranza è che possa confrontare rapidamente gruppi di qualsiasi tipo.

"Non conosciamo un tale teorema, ma abbiamo motivo di credere che qualcosa del genere dovrebbe essere vero", ha detto Josh Grochow dell'Università Colorado, Boulder.

Confronto Confronti

Per determinare se due cose sono uguali in modo preciso, devi prima definire "lo stesso". Due stringhe di numeri potrebbero essere considerate uguali se contengono semplicemente le stesse cifre o potrebbero aver bisogno di avere le stesse cifre nello stesso ordine.

L'isomorfismo è un tipo particolare di identità che emerge molto in matematica. Quando due oggetti sono isomorfi tra loro, significa approssimativamente che contengono gli stessi elementi e che questi elementi hanno la stessa relazione tra loro.

I grafici - raccolte di vertici (punti) collegati da bordi (linee) - forniscono un modo visivo accessibile per vedere come può essere l'isomorfismo. Due grafi sono isomorfi se puoi abbinare i vertici in un grafo con i vertici nell'altro, in modo tale che i vertici che sono collegati da un bordo nel primo grafo siano collegati da un bordo nel secondo. I grafici isomorfi possono apparire diversi in superficie, ma condividono una struttura sottostante.

I gruppi sono più astratti dei grafici, ma sono comunque suscettibili di confronto per isomorfismo. Un gruppo è una raccolta di elementi, come i numeri, che possono essere combinati tra loro in base a qualche operazione in modo che anche il risultato sia nella raccolta. Ad esempio, puoi avere un gruppo i cui elementi sono i numeri interi - tutti i numeri interi positivi e negativi, più zero - e la cui operazione è l'addizione: aggiungi due numeri interi qualsiasi e il risultato è sempre un altro numero intero.

Due gruppi sono isomorfi se puoi accoppiare ciascun elemento di un gruppo con un elemento dell'altro, in modo che il risultato dell'operazione su due elementi del primo gruppo sia coerente con il risultato dell'operazione sui valori equivalenti di quegli elementi nel secondo gruppo.

Ecco un semplice esempio di due gruppi, ciascuno con due elementi, che sono isomorfi tra loro. Il primo gruppo è costituito dai numeri 0 e 1 e il secondo gruppo è costituito dalle lettere a ed b. Entrambi i gruppi contengono un'operazione per combinare gli elementi del gruppo in un modo specifico, con i risultati esposti nelle tabelle seguenti.

I gruppi sono isomorfi perché 0 si accoppia con a, 1 coppia con b, e la relazione strutturale prodotta dalla combinazione degli elementi è la stessa in entrambi i gruppi.

"Diciamo che due gruppi sono isomorfi se sono fondamentalmente equivalenti", ha detto Sun.

Progresso sbilanciato

L'isomorfismo è un concetto importante in matematica - dove i grafici e i gruppi sono ampiamente presenti - perché consente ai matematici di guardare oltre le differenze superficiali e concentrarsi sui modi in cui gli oggetti correlati possono effettivamente essere gli stessi. Ma è fondamentale anche nell'informatica; i ricercatori non solo cercano algoritmi che determinano se due oggetti sono isomorfi, ma misurano anche la velocità di esecuzione di tali algoritmi.

Quella misurazione può essere complicata. La velocità di un algoritmo si basa su come il suo tempo di esecuzione cambia con la dimensione degli oggetti su cui sta lavorando. Immagina, ad esempio, di avere due coppie di gruppi. In una coppia, ogni gruppo contiene cinque elementi. Nell'altro, ogni gruppo contiene 10 elementi.

Ti aspetteresti che un algoritmo impieghi più tempo per determinare se i gruppi con più elementi sono isomorfi. Ma quanto tempo ancora? Ci vorrà il doppio del tempo? 5² più a lungo? 2⁵ più a lungo? Queste domande corrispondono a importanti classificazioni generali della velocità algoritmica: possono funzionare in tempo lineare (il che significa in questo caso che impiega il doppio del tempo), tempo polinomiale (5² più lungo) e tempo esponenziale (2⁵ più a lungo).

Gli informatici sanno in quale categoria di velocità rientrano la maggior parte delle domande di calcolo, ma non tutte.

"La maggior parte sono le più facili o le più difficili [tipo di domanda], ma ci sono ancora diverse eccezioni che sono sconosciute", ha detto Sun. L'isomorfismo del grafico e del gruppo sono tra quelle eccezioni, che è ciò che li rende così interessanti da studiare.

Nelle 1970s, Roberto Tarjan della Princeton University si è reso conto che esiste un algoritmo in grado di determinare se due gruppi qualsiasi sono isomorfi con un tempo di esecuzione di $latex n^{{(log,n)}}$, dove n è il numero di elementi in ciascun gruppo. Questo è chiamato un algoritmo di tempo quasi polinomiale e nella gerarchia dei tempi di esecuzione è migliore del tempo esponenziale (2ⁿ) ma peggiore del tempo polinomiale (n²). Questa è approssimativamente la stessa velocità dell'algoritmo di isomorfismo del grafico di Babai, ed è ancora il meglio che possiamo fare per i gruppi quasi 50 anni dopo.

"Significa all'incirca che non ci sono stati progressi per mezzo secolo", ha detto Sun.

Al momento del risultato di Tarjan, il problema dell'isomorfismo di gruppo era più ampiamente studiato rispetto alla versione del grafico. Oggi è capovolto, in parte perché l'isomorfismo del grafico ha stimolato innovazioni entusiasmanti mentre l'isomorfismo di gruppo si è bloccato.

"Tutti i nostri strumenti sono stati molto lenti per anni ed è stato difficile sfruttare ciò che sappiamo sull'algebra [dei gruppi]", ha affermato James Wilson dell'Università Statale del Colorado.

Ma nonostante questa disparità in corso, i due problemi hanno una connessione più profonda della somiglianza dei loro nomi: il problema dell'isomorfismo di gruppo (almeno in questa formulazione) si riduce al problema dell'isomorfismo del grafo. Ciò significa che qualsiasi algoritmo in grado di risolvere il problema del grafico può anche risolvere il problema del gruppo in un tempo simile. Non è vero il contrario: i progressi sul gruppo non implicano i progressi sul grafico. Ma la mancanza di progressi sul problema dei gruppi ha pesato sui matematici che cercavano guadagni proporzionati sul problema dei grafi. Come puoi realizzare una cosa più difficile se prima non riesci a realizzare qualcosa che è strettamente correlato e sembra ancora più facile?

"In altre parole", ha detto Sun, "per migliorare ulteriormente l'isomorfismo del grafico, l'isomorfismo di gruppo è un grosso collo di bottiglia".

Un problema trasformato

Quando il progresso su un problema si blocca tanto quanto lo è stato per l'isomorfismo di gruppo, di solito è necessaria l'invenzione per sbloccarsi. "Quando hai un grande anticipo, dovrebbe essere un'indicazione che c'è una nuova idea", ha detto Grochow.

Il lavoro di Sun contiene alcune idee che implicano il targeting di un tipo importante di gruppo e la ricerca di un modo intelligente per suddividere quei gruppi in pezzi per confrontarli.

Vengono chiamati i gruppi per i quali funziona l'algoritmo di Sun p-gruppi di classe 2 ed esponente p. Sono simili ai gruppi in cui il prodotto di due elementi è un altro elemento e il prodotto rimane lo stesso indipendentemente dall'ordine in cui li moltiplichi. Ma ciò che conta davvero è ciò che rappresentano per il problema generale dell'isomorfismo di gruppo. Questi gruppi hanno una struttura molto semplice, il che significa che dovrebbero essere facili da confrontare. Ma nonostante questa semplicità, i ricercatori non avevano trovato un modo per velocizzare l'algoritmo. Fino a quando non potevano, sembrava senza speranza apportare miglioramenti per la questione generale dell'isomorfismo di gruppo.

Sun ha iniziato cambiando l'impostazione dai gruppi alle matrici, matrici di numeri che fungono da oggetti fondamentali nell'algebra lineare. Ciò è stato possibile grazie a un teorema degli anni '1930 chiamato corrispondenza di Baer, ​​che trasforma questa versione della questione dell'isomorfismo di gruppo in un problema perfettamente analogo sulle matrici. In particolare, Sun ha lavorato con spazi di matrici, che sono raccolte di matrici con una proprietà speciale: la combinazione (lineare) di due matrici qualsiasi nello spazio è uguale a un'altra matrice nello spazio.

In altre parole, questi spazi sono strutturati in modo molto simile ai gruppi. Quindi, invece di cercare di capire quando due gruppi sono isomorfi, Sun potrebbe semplicemente provare a capire quando due spazi di matrici sono isometrici - una nozione di isomorfismo degli spazi di matrici che corrisponde a quella dei gruppi.

Sun non è stato il primo ricercatore ad adottare questo approccio, ma è stato il primo a introdurre un passaggio aggiuntivo: dividere uno spazio di matrice in due parti. Un pezzo è il nucleo dello spazio, in cui tutte le matrici sono semplici. L'altro pezzo è lo spazio che circonda quel nucleo, in cui tutte le matrici sono particolarmente complesse. Questo spostamento corrisponde alla suddivisione di un gruppo in sottogruppi che contengono solo una parte degli elementi totali.

Sun ha quindi applicato diversi metodi algoritmici a ciascuno di questi pezzi. Il nucleo ha una struttura semplice, quindi ha utilizzato una caratterizzazione della struttura per rappresentarla in modo più organizzato. Lo strato esterno è più complesso, quindi non esiste un modo ovviamente veloce per confrontarlo con un altro. Invece, il metodo di Sun adotta un approccio chiamato individualizzazione e perfezionamento per escludere la maggior parte dei modi possibili di mappare uno strato esterno sull'altro e quindi utilizza un computer per elaborare tutti i modi possibili rimanenti per determinare se esiste una corrispondenza isomorfa.

Il metodo è simile nello spirito a come potresti risolvere un sudoku. Ci sono alcuni quadrati i cui valori potenziali sono vincolati da ciò che già conosci (il nucleo dello spazio della matrice), permettendoti di riempirli rapidamente. Poi ce ne sono altri (lo strato esterno) che hanno meno vincoli, ma che puoi capire semplicemente provando tutti i possibili valori - e fintanto che non ci sono troppi di questi tipi di quadrati, puoi ancora risolvere il puzzle in un ragionevole lasso di tempo.

"Riempio tutte le cose che posso dire rapidamente che sono vincolabili, e ora potrei tornare indietro e provare il mio cuore sulle scatole mancanti", ha detto Wilson. "Se hai ristretto l'ambito, ora è un buon momento per cambiare marcia e utilizzare il computer per cercare i valori giusti."

La svolta di Sun stava dimostrando che è sempre possibile eseguire questa divisione per gli spazi di matrice corrispondenti a p-gruppi di classe 2 ed esponente p. Ha poi dimostrato che dopo una tale divisione, una combinazione di tecniche algoritmiche rende possibile determinare se due spazi sono isomorfi in $latex n^{{(log,n)}^{5/6}}$ tempo, un valore che è leggermente inferiore al metodo $latex n^{{(log,n)}}$ di Tarjan. (Entrambi gli algoritmi includono anche termini costanti, che non hanno un grande effetto sul runtime e che abbiamo tralasciato per chiarezza.)

Il risultato non determina in quale categoria di velocità rientri l'isomorfismo; è ancora da qualche parte tra il tempo esponenziale e polinomiale. Ma Sun l'ha spinto leggermente più vicino al lato polinomiale delle cose, e c'è motivo di credere che dovrebbe essere possibile più di questo. Dopotutto, il suo lavoro fornisce agli informatici un algoritmo di isomorfismo di gruppo più veloce per il tipo più difficile di gruppi, aumentando la possibilità che una simile accelerazione possa essere alla portata di gruppi di ogni tipo.

“Se riesci a risolverlo per p-gruppi, probabilmente puoi risolvere tutto ", ha detto Grochow. "Forse."