Karim lavora per un corriere espresso: con il suo furgone consegna pacchi e buste per conto di un'organizzazione avanzatissima dal punto di vista telematico ed informatico. Ogni giorno deve consegnare un certo numero, facciamo 20 oggetti in 20 indirizzi diversi, per cui avrà da percorrere un circuito, con partenza ed arrivo nel magazzino, formato da 20+1 tappe. Karim è un tipo pignolo: gli è saltato il ticchio di chiedere la sequenza ottimale, quella che può fargli risparmiare tempo, benzina, gomme, etc. Ma quell'antipatico del ragioniere gli ha risposto picche. Perchè?

Quello di Karim è un esempio del Traveller Salesman Problem, o TSP, un problema che è considerato difficile, perchè ad oggi non si conosce un algoritmo polinomiale (collegato polinomialmente alla dimensione n del problema, e quindi veloce) che possa risolverlo. Se volesse risolvere il problema, la ditta dovrebbe per prima cosa, e già qui non sarebbe facile, munirsi di una tabella enorme riportante le distanze tra ogni via della città e tutte le altre. Se rappresentiamo ogni tappa di Karim con una lettera dell'alfabeto, un esempio di percorso, detto ciclo hamiltoniano, può essere il seguente:

abcdefghijklmnopqrstua,

abcdefghijklmnopqrsuta,

se associamo ad ogni passaggio di lettera la distanza tra gli indirizzi estratta dal tabellone di cui sopra, e le sommiamo, possiamo associare ad ogni percorso possibile la distanza totale da percorrere, e quindi indirettamente il suo costo. Il metodo di soluzione cosiddetto della "forza bruta" consiste nell'analisi di ciascun percorso possibile, nel calcolo del suo costo, e nel confronto tra queste soluzioni possibili, alla ricerca di quella minore, e quindi ottima.

Quanti percorsi dovranno essere analizzati? Il loro numero è 20! (venti fattoriale), cioè 20x19x18x17... x ...3x2x1. il risultato è 243290200817640000. Detto così non sembra un granchè. Per chi mastica di crittografia e sicurezza, corrisponde circa a trovare una password composta da 8 caratteri da 8 bit, cioè password del tipo µ2«K<+;E.

Dunque, un calcolatore, con un processore di ultima generazione, col clock ad almeno un paio di gigahertz, equipaggiato con un software velocissimo, come AZPR, può analizzare fino a 30 milioni di combinazioni al secondo.

Per trovare la soluzione ottima, questa combinazione hardware-software impiegherà:

81.096.733.606 secondi,

cioè 1.351.612.227 minuti,

cioè 22.526.870 ore,

quindi 938.619 giorni,

perciò 2.571 anni e mezzo.

Questi sono i limiti della forza bruta: di fronte ad un problema così banale la best available technology dell'umanità va in crisi.

Naturalmente esistono algoritmi più efficienti, esiste la possibilità di collegare più elaboratori e farli lavorare contemporaneamente, e grazie a questo si può ampliare la dimensione del problema risolvibile in tempi decenti. Ma la sostanza non cambia: alcuni tipi di problemi, anche con dimensioni attorno al 50, non solo non sono praticamente risolvibili attraverso gli attuali computer, ma si può ragionevolmente supporre che non lo saranno mai, qualunque sia il progresso futuro della velocità dei calcolatori.

Ma l'inventiva umana, il genio, ci viene in soccorso. Come? Primo, accontentandosi: può essere agevole trovare soluzioni sub-ottimali, e queste sono spesso soddisfacenti. Secondo, cercando algoritmi più efficienti, tipo gli euristici, magari basati su interessanti interazioni col mondo della biologia, come quelli genetici o l'affascinante Ant Colony Optimization, che ricava un algoritmo dal comportamento apparentemente caotico delle formiche. Terzo, provando a rovesciare gli attuali paradigmi tecnologici: il calcolatore digitale ci intristisce? Proviamo con quello quantistico: per esso esistono già algoritmi efficienti a risolvere problemi ex-difficili (ottima documentazione disponibile anche su ZEUSNews).

Ma non è tutto: talvolta la matematica, quando ci mostra percorsi logici che possono essere utilizzati al di fuori di essa, ci insegna a vivere. Quando le variabili in gioco sono molte, un problema puramente combinatoriale come quello di Karim, assomiglia molto ai piccoli e grandi crucci della vita reale, come la droga, il terrorismo, la tutela dei diritti d'autore, gli insetti che infestano la mia albizia. In questi casi, può essere utile trarre insegnamento dalla teoria: la forza bruta difficilmente porta alla soluzione.