Chi è nato tra gli anni '70 ed '80 non può dimenticarsi del più famoso, ma al tempo stesso complicato, rompicapo in voga in quel periodo: si, si parla proprio del cubo di Rubik, che tanto ha fatto impazzire quelli della mia generazione (sempre se, come il sottoscritto, presi dallo sfinimento non staccavate gli adesivi per incollarli nella posizione giusta...). Bene, ci sono voluti 15 anni ma è finalmente dimostrato che qualsiasi combinazione del cubo può essere risolta in un massimo di 20 mosse, senza il bisogno di staccare gli adesivi. Tutto questo grazie ad un team che, combinando la potenza di calcolo di Google con alcune intuizioni matematiche, ha passato in rassegna tutte le 43 miliardi di miliardi di configurazioni che il cubo può assumere.
La principale innovazione è stata scoprire un metodo per risolvere così tante configurazioni tutte in una volta. Il risultato è stato chiamato "Numero di Dio", in quanto probabilmente neanche l'Altissimo potrebbe scendere al di sotto. Già nel 2008 questo numero era stato portato a 22, ma era chiaro che volerlo portare ulteriormente al di sotto avrebbe richiesto una qualche scorciatoia intelligente.
Per fare ciò, il gruppo di ricerca ha utilizzato tecniche matematiche derivate dalla teoria dei gruppi. Per prima cosa hanno suddiviso l'insieme di tutte le possibili configurazioni iniziali in 2,2 miliardi di gruppi, ognuno contenente 19.5 miliardi di configurazioni, sulla base della loro risposta dopo 10 possibili mosse. Questo raggruppamento ha permesso di restringere il campo a "soli" 56 milioni di gruppi, sfruttando anche le simmetrie presenti in un cubo. Questo procedimento ha comunque lasciato un numero enorme di configurazioni di partenza, pertanto i ricercatori hanno dovuto sviluppare un algoritmo per accelerare il processo.
I metodi precedenti, che permettevano di risolvere circa 4000 cubi al secondo, partivano da un insieme di mosse per poi determinare se la configurazione finale era più vicina alla soluzione. In caso contrario, le scartavano e ricominciavano con un altro insieme di mosse. L'intuizione fondamentale è stata quella di rendersi conto che queste mosse "dead-end" sono in realtà soluzioni di altre configurazioni di partenza, che hanno portato il gruppo di ricerca a sviluppare un algoritmo da ben 1 miliardo di cubi risolti al secondo. Si può pensare all'algoritmo in questi termini: si supponga di dover andare a trovare un amico in una città sconosciuta: si conoscono le indicazioni su quando svoltare a destra o sinistra ma non il punto di partenza. Se si partisse da un punto a caso sarebbe molto improbabile raggiungere la destinazione, ma adeguandole al corretto punto iniziale sicuramente si arriva. Allo stesso modo, l'algoritmo sviluppato adegua le mosse alla configurazione di partenza, permettendo di risolvere ogni gruppo di 19,5 miliardi di configurazioni in meno di 20 secondi.
Anche a queste velocità ci sarebbero voluti comunque 35 anni di calcoli utilizzando un normale computer. Ma, essendo stato possibile utilizzare la vasta rete di computer di Google, il problema è stato risolto nel giro di alcune settimane. Si sapeva da 15 anni che alcune configurazioni del cubo richiedevano appena 20 mosse per la soluzione, ed alcuni matematici sospettavano che non ne servissero di più. Ora, grazie a questo lavoro, è diventata una certezza.
Ricerche come queste mostrano come la matematica pura possa essere utilizzata per semplificare complessi problemi di calcolo, ed il cubo di Rubik, per la sua complessità, si presta bene ad essere il banco di prova per i metodi della teoria dei gruppi.
Nessun commento:
Posta un commento