Utilizzando gli scacchi e la geometria frattale per comprendere meglio la struttura di un tipo di cristallo particolarmente esotico, i fisici britannici e svizzeri hanno progettato un algoritmo che si è rivelato capace di produrre un labirinto di complessità assolutamente diabolica, il più difficile mai creato secondo loro.
Gli oggetti su cui sta lavorando questa squadra non sono infatti proprio cristalli in senso stretto: sono infatti quasicristalli. A differenza dei normali cristalli che sono incredibilmente abbondanti, anche questi quasicristalli lo sono eccezionalmente raro nel suo stato naturale. In effetti, ci sono solo una manciata di fonti naturali conosciute e sono tutte meteoriti.
Al di là della loro rarità, ciò che rende questi materiali così interessanti è la loro architettura. Gli atomi sono disposti in una struttura altamente organizzata e simmetrica, come i cristalli tradizionali. Ma a differenza di quest’ultimo, i gruppi di atomi non si ripetono periodicamente nello spazio seguendo uno schema semplice. Invece, mostrano tipi di simmetria molto più elaborati.
« I quasicristalli hanno tutte queste simmetrie che non potrebbero esistere nei cristalli, il che è piuttosto affascinante. È una branca della matematica molto bella, ma chiunque può apprezzarne la bellezza direttamente, senza bisogno di comprenderne i dettagli. », spiega Felix Flicker, coautore dello studio citato da Nuovo scienziato.
Cristallo, scacchi e matematica
Dato che ci sono così tanti esempi, la scienza ha ancora molto da imparare sulle particolarità dei quasicristalli. Per comprendere meglio questi alieni geometrici, il team di Flicker ha deciso di creare un algoritmo ultra specializzato per descriverne la struttura. E per raggiungere questo obiettivo si sono ispirati… ai fallimenti.
Il collegamento non è ovvio, ma la struttura dei quasi-cristalli presenta in effetti delle particolarità con un vecchio problema di logica basato sui movimenti del pezzo più singolare del re dei giochi da tavolo.
Questo cosiddetto puzzle del Cavaliere di Eulero inizia con un cavaliere posizionato su qualsiasi casella della scacchiera. L’obiettivo è fargli visitare tutte le altre scatole senza mai passare due volte dalla stessa. Quando tracciamo il percorso di questo ciclista, otteniamo quello che chiamiamo circuito hamiltoniano, vale a dire che passa una sola volta per tutti i punti di un grafico.
Tuttavia, si scopre che anche la struttura degli atomi nei quasicristalli segue questa regola. Ed è qui che il lavoro diventa interessante, perché questa somiglianza ci permette di comprendere il problema dal punto di vista della teoria della complessità.
Un’incursione nella teoria della complessità
In generale, trovare un circuito hamiltoniano è ciò che chiamiamo a Problema NP-completo. Questo termine designa un problema la cui complessità aumenta esponenzialmente con il numero degli elementi, al punto che diventa presto impossibile calcolare la soluzione con la forza bruta sulla nostra scala temporale. D’altronde, se ci troviamo di fronte ad una potenziale soluzione, è facile verificare velocemente se è valida, un po’ come un puzzle in cui basta osservare l’immagine finale.
La sfida consiste quindi nel trovare un modo per risolvere questi cosiddetti problemi NP-completi in un tempo ragionevole (o più precisamente in un cosiddetto tempo polinomiale). Ed è un problema che fa impazzire i matematici da decenni. In effetti, rientra addirittura nell’ambito di applicazione P=NP, uno dei famosi problemi del Premio del Millennio. Questo è un elenco di sette principali problemi di matematica che prevedono un premio di un milione di dollari per la loro soluzione. Finora solo una di queste, la congettura di Poincaré, è stata risolta (da Grigori Perelman nel 2010).
Questa equazione materializza una domanda quasi esistenziale per i matematici: Questi problemi complessi sono davvero così difficili da affrontare come sembrano, oppure esiste una soluzione generale semplice che nessuno ha ancora trovato per cercare una soluzione velocemente?
Se un giorno questa ipotesi P=NP venisse confermata, cosa tutt’altro che certa, le implicazioni sarebbero enormi. Ciò cambierebbe radicalmente la natura di una serie di problemi molto importanti per la scienza moderna, ma oggi considerati quasi intrattabili (vedi il nostro articolo qui sotto per maggiori dettagli).
Il punto importante è che tutti gli specialisti della teoria della complessità concordano su un punto: ritengono che se esiste un algoritmo per risolvere un singolo problema NP-completo in un tempo ragionevole (polinomiale), allora questo significa che esiste anche una soluzione relativamente semplice per TUTTI gli altri problemi NP-completi, compresi i circuiti hamiltoniani! E si scopre che molti di essi sono eccezionalmente importanti per la scienza moderna. Possiamo citare il problema del commesso viaggiatore, la cui rapida soluzione eliminerebbe immediatamente moltissimi enigmi logistici estremamente difficili, oppure la meccanismi di ripiegamento delle proteine che i team di DeepMind hanno affrontato utilizzando il machine learning.
Ora, risulta che il cavaliere di Eulero è a caso particolare. Sebbene i circuiti hamiltoniani siano generalmente problemi NP-completi, ce ne sono alcuni che possono essere risolti rapidamente con qualche gioco di prestigio matematico. Il cavaliere di Eulero è uno di questi: possiamo trovare rapidamente una soluzione utilizzando un metodo semplice, l’algoritmo di Warnsdorf. Poiché questo problema è strettamente legato alla struttura dei quasicristalli, gli autori di questo lavoro hanno quindi cercato un metodo analogo per applicarlo al proprio problema.
E ne hanno trovato uno, che ha permesso loro di generare questo labirinto incredibilmente difficile che illustra la disposizione degli atomi in questi materiali.
Non una prova di P=NP, ma interessanti applicazioni concrete
Secondo i ricercatori citati da ScienceAlertquesto lavoro potrebbe avere implicazioni molto concrete in settori quali l’ottica o la cattura del carbonio.
D’altra parte, ciò non significa affatto che il problema dei circuiti hamiltoniani sia stato risolto una volta per tutte; quanto al Cavaliere di Eulero, si tratta semplicemente di modo molto elegante di semplificare un problema molto specifico e in nessun caso una soluzione generale.
Per estensione, non è nemmeno una risposta all’ipotesi P=NP e a tutti gli altri problemi NP-completi… ma forse è un passo in quella direzione. Chi lo sa ; Se un giorno emergerà una soluzione rigorosa, questo lavoro potrebbe essere ricordato come uno dei pezzi che hanno aperto la strada a una delle rivoluzioni più importanti nella storia della matematica.
Il testo dello studio è disponibile qui.
Per non perdere nessuna notizia sul Journal du Geek, iscriviti su Google News. E se ci ami, abbiamo una newsletter ogni mattina.
