sabato 8 marzo 2008

Il labirinto

Il termine “labirinto” è di origine incerta ed antica. Nella classicità, un labirinto era un edificio, almeno in parte sotterraneo, con una struttura che creava intenzionalmente confusione. Erodoto considerava il labirinto egiziano presso Crocodilopoli (completato nel 1795 a.C.) una meraviglia più grande delle piramidi. Conteneva 3000 stanze, metà al di sopra e metà ad di sotto del livello del terreno. Una foresta di pilastri si estendeva a perdita d’occhio. Erodoto visitò la metà superiore, ma non gli fu permesso di scendere sotto. La progressiva decadenza di questo labirinto è narrata da numerosi storici antichi. Le fondamenta, dissotterrate nel 1888, misurano 240 per 300 metri.

Tuttavia il labirinto più famoso è quello del Minotauro nell’isola di Creta. Nella leggenda greca, il Minotauro, un mostro con corpo umano e testa di toro, viveva al centro di un vasto labirinto progettato da Dedalo per il re cretese Minosse. Dopo la vittoria cretese su Atene, Minosse decretò che i cittadini di Atene sacrificassero sette giovinetti e sette fanciulli al Minotauro ogni nove anni. Nessuno dei giovani che entrarono nel labirinto riuscì mai a venirne fuori. Il principe ateniese Teseo si offrì per il sacrificio. La figlia di Minosse, Arianna, gli consigliò di svolgere un filo di seta entrando nel labirinto, in modo da poter ritrovare l’uscita. In questo modo Teseo uccise il Minotauro e pose fine al tributo.

Il moderno “labirinto” è quasi sempre un giardino dai percorsi intricati delimitati da siepi di carpino o tasso.

Il labirinto rimane un oggetto misterioso. Il problema di farsi strada in un labirinto si dice che è NP-completo: fa parte cioè di una serie di problemi universali in grado di confondere il più potente computer.

La NP-completezza è una classe di problemi che ossessiona i programmatori di computer da oltre quattro decenni. I computer, fin dalla loro invenzione, sono diventati sempre più veloci e potenti. I computer in uso negli ultimi mesi sono circa 1000 volte più potenti di quelli di dieci anni fa e addirittura 30.000.000 di volte più potenti di quelli degli ultimi anni Cinquanta. Alla metà degli anni Sessanta, però, gli esperti di informatica cominciarono a capire che qualcosa non andava. Certi problemi sono estremamente difficili da risolvere mediante computer (o qualsiasi altro metodo conosciuto). Impiegare processori più veloci non fa poi tanta differenza come si potrebbe sperare. Questi problemi furono chiamati “intrattabili” o “intrinsecamente difficili”.

Ci possiamo quindi porre la seguente domanda: esiste un metodo generale che risolvere un qualsiasi labirinto? La risposta è si; anzi, esistono diversi metodi, in effetti. In realtà non tutti i labirinti sono degli enigmi, ad esempio il labirinto della cattedrale di Chartres è lineare. Non ha pareti ma è disegnato con marmo bianco e azzurro sul pavimento.

Nella geografia del labirinti, un nodo è una biforcazione, un punto in cui i sentieri si incontrano e bisogna prendere una decisione. L’entrata, la meta finale e i vicoli ciechi sono pure considerati dei nodi. Il segmento di sentiero fra due nodi è chiamato ramo. Una semplice pianta di qualsiasi labirinto può mostrare i nodi sottoforma di punti collegati da linee che rappresentano i rami.

Non vi è alcun modo rapido di risolvere un labirinto sconosciuto (cioè di cui non ne conosciamo a priori la pianta), nessun modo di sapere, prescientemente, quali sentieri favorire. La cosa migliore la fare è esaminare quasi tutti i sentieri fino a trovare la meta.

Se usiamo uno qualsiasi degli algoritmi trovati dagli esperti di informatica, il tempo impiegato a esplorare il labirinto cresce esponenzialmente con il numero di nodi da esplorare. Supponendo di poter esplorare un ramo ogni minuto, se il nostro labirinto ha solo quattro nodi, impiegheremo circa 5 ore per esplorarlo! Ma se ne ha dieci ci vorranno 38, 4 giorni. E se ne avesse 45? Allora in questo caso basterebbero 17,7 miliardi di anni! La cosa vi fa impazzire? Ovvio, non ci si aspetta che il tempo di soluzione del labirinto cresca così rapidamente all’aumentare della complessità dello stesso. Basti pensare che i cifrari che proteggono i dati delle banche o delle installazioni militari si basano sulla insolubilità di problemi NP-completi. Anche il più veloce computer esistente al mondo per trovare tutte le lettere e numeri di una chiave cifrata impiegherebbe milioni o persino miliardi di anni.

In definitiva possiamo dire che i problemi NP-completi sono una zona d’ombra della nostra conoscenza, perché ci mettono di fronte ad un limite intrinseco della nostra logica. Così come è praticamente irrisolvibile un labirinto che superi certe dimensioni, così lo sarà un problema logico di complessità maggiore di un certo livello. Ne consegue, evidentemente, che anche le nostre deduzioni riguardo alla realtà saranno fatalmente limitate.

Possiamo stare certi, dunque, che nessuno nell’Universo conosce tutto.

 

Leggi tutto:

>> Matrix e i cervelli in provetta

>> Il tempo, questo sconosciuto...

>> Ipnosi: sfatiamo alcune false convinzioni.

>> Perché al sole ci abbronziamo?

>> Quante calorie si consumano facendo sesso? In molti me lo hanno chiesto ed io li ho accontentati.

>> Vuoi sapere quale sport fa consumare più calorie? Guarda questa tabella.

>> Filmato di una autopsia autentica (solo per chi ha lo stomaco forte)

>> Piante aliene

>> Achille in volo con Jonathan. Un uomo vola insieme ad un gabbiano (filmato)

>> Le foto dei 10 pesci più orrendi del mondo!

>> Spettacolare filmato di un superfluido che attraversa il vetro come se fosse un colabrodo!

>> Queste pazze, pazze nubi! (immagine)

>> Gli astronomi hanno scoperto il diamante più grande di tutti i tempi. Dieci miliardi di trilioni di trilioni di carati!

>> Dark Resurrection: per i fans di Guerre Stellari.

>> Perché le persone vogliono guadagnare su Internet?

>> I "Magnestars" (stelle magnetiche) sono tra gli oggetti più misteriosi dell'Universo.

>> Le immagini da satellite mostrano le violenze nel Myanmar (Birmania).

Nessun commento:

Posta un commento

Lascia un tuo commento!

Space X Starship: il nuovo tentativo di lancio del 18 novembre 2023.

Vediamo un frammento della diretta del lancio dello Starship del 18 noembre 2023. Il Booster 9, il primo stadio del razzo, esplode poco dopo...