 |
| Statua di al-Khwarizmi a Khiva, in Uzbekistan |
La
forma latinizzata di "al-giabr wa l-mukabalah", titolo di
un manuale arabo apparso intorno all'820 d.C., suona "Algebra et
almucabala"; attraverso questo manuale i matematici occidentali
vennero a conoscenza delle cifre arabico-indiane. Non solo il titolo
del libro, ma anche il nome dell'autore continua a vivere nel
linguaggio specialistico odierno: al-Khwarizmi è diventato
algoritmo, e con ciò senz'altro sinonimo di ogni
procedimento di calcolo. Letteralmente, il titolo arabo significa
all'incirca "il trasporto", e indica la manipolazione delle
equazioni per il calcolo. L'algebra conservò questo significato -
nel senso più esteso - fino a tutto il XIX secolo.
Tuttavia,
la scoperta di oggetti matematici quali vettori, matrici, ecc. con i
quali si possono fare calcoli simili a quelli che si fanno con i
numeri, ampliò da un lato il dominio di indagine dell'algebra, e
dall'altro venne interpretata come un indizio del fatto che dietro i
diversi oggetti di calcolo c'è un nucleo comune, la scoperta del
quale deve fornire risultati validi per tutti gli oggetti speciali.
Postilla
E' l'incipit della voce Algebra
nel volume 15 Matematica I dell'Enciclopedia
Feltrinelli Fischer (Feltrinelli, 1967). Ne è autore il matematico
tedesco Tietz. La traduzione è del curatore del volume Lucio
Lombardo Radice.
A distanza di quasi 50 anni sono stati fatti molti passi avanti, ma la matematica e gli algoritmi sono rimasti comunque intimamente legati. Uno dei problemi moderni piu’ affascinanti e di grande levatura teorica (ma con effetti pratici importantissimi) ha il curioso nome di “P versus NP”.
RispondiEliminaSemplificando, ci sono problemi per cui esistono algoritmi che possono controllare in tempi brevi se una soluzione e’ corretta, ma per cui non sono noti algoritmi capaci di trovare in tempi altrettanto brevi una soluzione ottimale al problema. Tali problemi si dicono NP, mentre la classe dei problemi risolvibili in tempo polinomiale e’ nota come P.
La grande domanda, ad oggi senza risposta, e’ se ogni problema NP in realta’ e’ P-equivalente, ovvero: Quando esiste un modo per verificare velocemente se una soluzione al problema e’ corretta, esiste sempre (anche se non e’ noto) un modo veloce di risolvere il problema? C’e’ un modo per arrivare in maniera meccanica dall’algoritmo di verifica della soluzione all’algoritmo di soluzione del problema?
La risposta, sia positiva che negativa, avrebbe effetti importanti sulla matematica e l’informatica. Ad esempio se P e’ equivalente ad NP, la crittografia come la conosciamo oggi potrebbe risultare in futuro del tutto inefficace a proteggere i dati.
Salvatore Sanfilippo