Ecco le formule che animano i pc

da La Stampa
del 26\03\2008

NEWS
26/3/2008 - INTERVISTA AL COMPUTER SCIENTIST

Ed ora, un po' di pubblicità

Ecco le formule che animano i pc

Juris Hartmanis: "Vi racconto i rompicapi della computazione
come i problemi P e NP"

FRANCESCO DE PRETIS

Juris Hartmanis, fisico e matematico, è un esempio di
altissimo livello di come la «scienza dei numeri» estenda le
sue applicazioni a tutte le discipline. E' stato ospite al
Festival della Matematica che si è tenuto dal 13 al 16 marzo
all’Auditorium Parco della Musica di Roma.

Professor Juris Hartmanis, lei è considerato uno dei padri
dell’informatica. Qual è il suo rapporto con i computer?
«Quando iniziai a interessarmi all’informatica era il ‘67 e
lavoravo nei laboratori della General Electric a Schenectady
(New York), ma non avevamo nemmeno un computer! Poi, alla
Cornell University, mi sono occupato di computazione frattale
sulla scia di Benoit Mandelbrot. A differenza di Mandelbrot,
però, penso che un computer avrebbe potuto essere d’aiuto per
i grandi del passato. Newton o Riemann avrebbero fatto
scoperte ancora maggiori di quelle che - solo con le loro
menti - sono stati in grado di raggiungere».

Come spiegherebbe la sua più grande scoperta nell’informatica,
il teorema di gerarchia temporale?
«Io e Dick Stearns discutevamo spesso della teoria
dell’informazione di Shannon, una teoria matematica che, per
esempio, spiega come viene veicolata l’informazione vocale in
una chiacchierata tra due telefoni distanti migliaia di
chilometri».

E quindi?
«Shannon aveva ricavato una relazione matematica di quanta
informazione può essere trasmessa attraverso un canale
“rumoroso”, mentre io e Dick volevamo trovare una teoria
quantitativa di quanto “sforzo computazionale” serve per
risolvere specifici problemi, vale a dire quanto impegno deve
mettere un computer per risolvere alcuni compiti, come
moltiplicare due numeri o fattorizzarli, trovando i numeri
primi che li costituiscono. Come prime unità di misura di
questo “sforzo” scegliemmo il tempo di computazione o il
numero di operazioni svolte dal computer per risolvere un
determinato problema e scoprimmo che il minimo crescere della
soglia temporale di computazione portava a una nuova classe di
problemi, che non potevano essere risolti in un tempo minore.
Ne nacque così una vera e propria classificazione di problemi
matematici che non era mai emersa precedentemente in
informatica, la cosiddetta “gerarchia temporale”».

Parte dei suoi studi ha portato ai cosiddetti «problemi P e
NP», un mistero sul quale pesa una taglia di un milione di
dollari: perché risolvere questo rompicapo è così difficile?
«A differenza dei problemi P, i problemi NP non sono
risolvibili in un tempo almeno inferiore all’età del nostro
universo nemmeno dal più grande supercomputer mai costruito
dall’uomo: sono l’essenza stessa di un rompicapo.

Pensa che la computazione quantistica sarà d’aiuto?
«Secondo me, il “quantum computing” è un grande esperimento ma
finora le ricerche in quel campo hanno contribuito di più a un
ulteriore sviluppo della meccanica dei quanti piuttosto che
dell'informatica».

+ Robert Aumann: ”I numeri per fare la pace” GABRIELE BECCARIA