Guida pratica alle superpermutazioni minimali

Supponiamo adesso di voler vedere gli episodi nell’ordine corretto, ovvero: quanti episodi dovrai guardare per farlo? Se la serie fosse composta da soli 2 episodi, basterebbe vedere il primo, il secondo e poi di nuovo il primo, e qualunqu fosse l’ordine corretto ci ritroveremmo “a cavallo”. Chiaramente si tratta di un lower bound, di un limite inferiore, perchè non posso fare questa attività senza vedere almeno due volte l’episodio 1 e preservando la condizione data. Il bello è che, a questo punto, se volessimo estendere il ragionamento per n intero generico maggiore di 2, il numero numero minimo di episodi che dobbiamo guardare per una serie televisiva di n episodi non si sa ancora bene come si calcoli. È infatti uno dei grandi problemi aperti della matematica di oggi.

Il problema di Haruhi

Questa curiosa denominazione prende spunto dalla light novel nota in Italia con il titolo La malinconia di Haruhi Suzumi, per cui è successa una cosa abbastanza curiosa: i suoi 14 episodi sono stati trasmessi in ordine diverso da quello cronologico, sia in TV che in DVD. In questo caso avremo che n=14 ed è facile rendersi conto che la superpermutazione minimale non sia banale nè da scrivere, nè tantomeno da concepire anche solo numericamenteo come lower bound. Come fare a vedere tutta la serie nel minor tempo possibile, senza sapere l’ordine cronologico effettivo degli episodi?

Nel 2018 è stato dimostrato che un lower bound valido è:

L >= n! + (n-1)! + (n-2)!

il tutto concepito mediante una complessa dimostrazione costruttiva – che trovate al link indicato. Il bello è che il tutto era avvenuto su 4chan, con tutte le conseguenze del caso (e la disconferma che il dark web sia una brutta cosa a prescindere): come citare un teorema effettivamente valido non pubblicato su una rivista scientifica? Questo risultato è stato un importante contributo alla teoria delle superpermutazioni, e mette in discussione in meccanismo del peer review che, prima o poi, dovrà esplicitamente prevedere circostanze del genere.

Non vale il bias di autorità, in sostanza: per le dimostrazioni matematiche vale “solo” la validità logica del ragionamento che si sta facendo, per cui un rispettato luminare matematico potrà avere tranquillamente torto, quanto un anonimo troll di Internet potrebbe avere ragione, come è successo in questo caso.

Ulteriori sviluppi: problema del commesso viaggiatore

L’argomento è molto complesso e poi sembrare astratto, al più un vezzo da nerd, ma non è così: un noto problema di teoria dei grafi come quello del “commesso viaggiatore” sembra direttamente collegato a quello delle superpermutazioni minimali.

In un mondo ossessionato dal risparmio ad oltranza e dal non voler sprecare risorse, vale la pena leggere fino in fondo: il problema del commesso viaggiatore (Travelling Salesman Problem o TSP) è un problema matematico che riguarda un commesso che deve visitare varie città in modo efficiente, ovvero: passando una sola volta per ognuna di esse e tornando alla base a fine giornata. Nel caso di un grafo con 5 nodi, possiamo immaginare che ci siano 5 città e il commesso deve trovare il percorso più breve per visitarle tutte, tornando infine alla città di partenza. Ad esempio:

{1,2,5,3,4,1}

Il problema è complicato perché ci sono molte possibili combinazioni di percorsi che il commesso può seguire, e dipendono dal costo del tragitto da ogni nodo ad ogni altro. L’obiettivo del problema resta quello di trovare il percorso più breve possibile, in modo che il commesso non sprechi tempo e/o risorse visitando città inutilmente e/o facendo percorsi più lunghi del necessario.

Suona familiare? Il TSP chiede, dato un elenco di città e le distanze tra queste città, di trovare il percorso più breve che visiti ogni città esattamente una volta. Nel problema della superpermutazione, ci veniva chiesto di trovare la stringa più breve contenente tutte le permutazioni di un insieme di n elementi. Con un piccolo sforzo immaginifico, invece di dire che dobbiamo trovare la stringa più breve contenente tutte le permutazioni, potremmo riformulare che dobbiamo trovare il percorso più breve che visita ogni permutazione esattamente una volta. Per poter formulare il problema in questo modo, avremmo bisogno di un elenco di tutte le permutazioni e delle “distanze” tra di esse. Creare un elenco di tutte le permutazioni è abbastanza facile. Prima abbiamo fornito l’elenco per il caso di 3 elementi: 123, 132, 213, 231, 312, 321. Rimane da capire cosa intendiamo per “distanza” tra le permutazioni, a questo punto.

Si è scoperto che il problema delle superpermutazioni minimali è di fatto equivalente a trovare il percorso più breve attraverso tutte le permutazioni, dove la distanza tra due permutazioni è data dal numero di caratteri aggiuntivi necessari per formare la loro superstringa. E vale un curioso concetto di distanza, perchè abbiamo visto che 213 non ha lo stesso peso di 312, per quanto camminare da A verso B richieda in genere lo stesso tempo che andare da B verso A, nel mondo reale. Lo sforzo concettuale che bisogna fare in questo caso che i nodi saranno le singole permutazioni, e che “la lunghezza del tragitto” è determinata dal numero di archi del grafo (citta, percorsi) che andiamo ad attraversare.

Ed è a questo punto che dovrebbe essere chiaro perché ci siamo occupati di problemi così difficili: perché possono avere un impatto su problemi reali in modo sostanziale, E perché possono essere un modo alternativo per riformulare problemi complessi in un’ottica più agevole. Questo naturalmente vale per molti altri casi di problemi reali, generalizzando, risolti mediante strumenti informatici e opportune codifiche a supporto.