Per rispondere alla domanda, è opportuno iniziare chiarendo che cosa sia un sistema assiomatico e come (e perché) la definizione di sistema assiomatico sia mutata nel corso del XIX secolo. Seppure di lunghezza non trascurabile, data la complessità dell’argomento, quel che segue è, comunque, un racconto schematico e, dunque, (necessariamente) largamente incompleto.In generale, possiamo pensare a una teoria matematica come a una struttura che si occupa di individuare le proprietà (espresse sotto forma di affermazioni) di un certo universo di oggetti, che chiameremo U. Ad esempio, potremmo considerare una teoria che si occupa dei numeri naturali e una delle proprietà di tale universo potrebbe essere “tutti i numeri pari sono divisibili per 2”. Naturalmente, possiamo costruire anche affermazioni che non esprimono proprietà di U come, relativamente all’universo dei naturali, l’affermazione “tutti i numeri pari sono divisibili per 3”. La teoria deve, dunque, permettere di discernere fra proprietà e non-proprietà dell’universo (o, equivalentemente, fra affermazioni vere e affermazioni false).
Le teorie matematiche differiscono le une dalle altre non soltanto rispetto all’universo del quale si occupano (figure geometriche piane, oppure numeri naturali, oppure funzioni reali continue), ma anche per il metodo che utilizzano per stabilire se talune affermazioni che possiamo fare sugli oggetti che popolano l’universo esprimono proprietà vere oppure proprietà false di quegli oggetti.
La geometria euclidea è una teoria matematica il cui universo è quello delle figure geometriche e che, per accertarne le proprietà, utilizza il metodo assiomatico: a partire da un gruppo di (pochi) oggetti elementari (chiamati concetti primitivi), che non vengono definiti perché assunti intuitivamente noti, e da un insieme di proprietà di questi oggetti (chiamate assiomi o postulati), che si assumono vere perché rispondenti a criteri intuitivi di verità, vengono definiti nuovi oggetti e dimostrate nuove proprietà applicando intuitivamente le regole della deduzione (sostanzialmente, per fissare le idee, il modus ponens citato nel libro). Il metodo utilizzato per derivare nuove proprietà dagli assiomi è, dunque, quello deduttivo, in base al quale il riferimento all’universo U è solo iniziale, allorquando si stabiliscono gli assiomi; il criterio giustificativo è quello semantico dell’evidenza dei soli assiomi. La geometria euclidea pone, dunque, le sue fondamenta su una serie di osservazioni intuitive. Tuttavia, una volta definiti i concetti primitivi e assunte vere le prime proprietà di questi oggetti, le nuove proprietà sono accertate sulla base dell’applicazione rigorosa (seppure praticata in modo intuitivo) delle regole di deduzione.
Comunque, nonostante il fascino esercitato sugli studiosi dalla splendida costruzione che è la geometria euclidea, le teorie matematiche che hanno visto la luce nel corso dei secoli e fino alla metà del XIX secolo, come, ad esempio, l’analisi infinitesimale, non erano basate sul metodo assiomatico. Erano, per l’appunto, teorie non assiomatiche. E nelle teorie non assiomatiche l’intuizione gioca un ruolo di gran lunga più rilevante di quanto non accada nella geometria euclidea. Proviamo a fare un esempio, magari un po’ forzato ma che può aiutarci a fissare le idee. Nessuno ci ha mai detto cosa sia un numero naturale (a meno che non abbiamo studiato il sistema assiomatico, appunto, di Peano): cos’è un numero naturale lo abbiamo sempre considerato noto a livello intuitivo. Si potrebbe obiettare che questo è equivalente a considerare tutti i numeri naturali come i concetti primitivi, ma c’è qualcosa che non funziona in questo approccio: Euclide ricorre a tre soli i concetti primitivi (il punto, la retta e il piano) e a partire da essi costruisce tutti gli altri oggetti contenuti nell’universo della teoria (angoli, poligoni, circonferenze, …). Assumere qualunque numero naturale come concetto primitivo della teoria significa, invece, che tutti gli oggetti che popolano l’universo della teoria sono concetti primitivi!
Ma perché non è stato utilizzato il metodo assiomatico anche per sviluppare l’aritmetica dei numeri naturali (e il calcolo infinitesimale, per dire)? Beh, è sufficiente provare a derivare la sequenza di deduzioni che, nell’aritmetica di Peano, permette di dimostrare che 1+1=2 per trovare una risposta a questa domanda… In effetti, le teorie non assiomatiche riescono a giungere a risultati intuitivamente veri (ossia, che ben si accordano alla nostra esperienza) senza dover ricorrere al sovraccarico della pedante sequenza di passi richiesti da una prova nel metodo assiomatico.
E, infatti, l’utilizzo di metodi non assiomatici sembrava funzionare piuttosto bene. Certamente, la matematica aveva fatto passi da gigante, pur senza ricorrere al metodo assiomatico. Sì, le cose parevano proprio funzionare bene, fino a quando non accadde qualcosa…
Nel corso dei secoli si erano succeduti innumerevoli tentativi di dimostrare il postulato delle parallele di Euclide (il suo V postulato) a partire dai primi quattro: in effetti, trattando questo postulato di questioni relative all’infinito (si può esser certi per davvero che due rette non si incontrano mai solo seguendo i loro percorsi fino… all’infinito), sembrava che assumerlo vero su una base intuitiva, in qualche modo, sminuisse la costruzione di Euclide e che, d’altra parte, apparendo evidentemente vera la proprietà che esso descrive, dovesse essere possibile desumerlo a partire dai primi quattro postulati. E fu così che, nel 1733, Giovanni Girolamo Saccheri pubblicò il trattato “Euclide ab omni naevo vindicatus” (“Euclide emendato da ogni neo”) nel quale era convinto di aver rimosso l’unico “neo” degli Elementi di Euclide, presentando una dimostrazione per assurdo del quinto postulato. Ma si sbagliava… In effetti, egli non pervenne ad alcun assurdo ma, piuttosto, inconsapevolmente, arrivò a descrivere due nuove geometrie. Tali, nuove, geometrie vennero riprese un secolo dopo da illustri matematici, del calibro di Gauss (che fu il primo, intorno al 1813, ad avere una chiara visione di una geometria coerente in cui il V postulato fosse sostituito da una sua negazione), Bolyai, Lobacevskij e Riemann (con il suo “Sulle ipotesi su cui si fonda la geometria” che venne pubblicato postumo nel 1867).
L’opera di Saccheri segnò un momento cruciale nella storia della matematica: essa aprì la strada all’idea di fondare la validità di una geometria sulla sua non contraddittorietà logica piuttosto che sulla sua evidenza intuitiva. Ma andiamo con ordine.
A valle delle nuove scoperte, si ponevano, ineluttabili, una serie di questioni: era ancora possibile credere nell’esistenza di un’unica Geometria? O, piuttosto, bisognava accettare che esistessero tante geometrie, diverse tra di loro? E, in quest’ultimo caso: come si ponevano di fronte all’evidenza di ciò che era osservabile, queste nuove geometrie? Ancora più urgentemente: ci si poteva ancora fidare dell’intuito per assegnare un significato a ciò che era evidentemente osservabile? Per potere accettare le nuove geometrie come teorie matematiche, era necessario modificare il metodo assiomatico, così come inteso nella geometria euclidea: o cercando nuove definizioni per i concetti di ‘evidenza’ e ‘intuito’ oppure rinunciando alla possibilità di farvi ricorso. Si scelse di seguire (da un certo momento in poi, almeno) la seconda strada e questa scelta, unita al fascino da sempre esercitato dalla geometria euclidea, indusse molti degli studiosi a muoversi nella direzione della riformulazione in termini assiomatici delle varie teorie non assiomatiche, in un senso, però, di gran lunga più formale che non nel sistema di Euclide: si passò dal metodo assiomatico della geometria euclidea (che, fino ad allora, era chiamato “metodo ipotetico-deduttivo” e al quale Hilbert, nel 1900, diede il nome di “metodo assiomatico”) al metodo assiomatico formale (da taluni indicato, semplicemente, come metodo assiomatico, riservando l’aggettivo “semiassiomatico” al sistema ipotetico deduttivo di Euclide).
In un sistema formale, ossia, in una teoria matematica che utilizza il metodo assiomatico formale, rimangono i i concetti primitivi, quelli che si accetta di non definire, e gli assiomi, cioè le affermazioni che si accetta di non dimostrare. Tuttavia, nessun significato intuitivo è associato tanto ai i concetti primitivi quanto agli assiomi: dei concetti primitivi si suppone solo di conoscere le mutue relazioni fissate dagli assiomi, ma non un loro significato indipendente. Sono le relazioni tra i concetti che hanno significato, non i concetti.
La Grundlagen der Geometrie, pubblicata nel 1899 da David Hilbert, è l’opera che ha dato impulso a questo modo di intendere la conoscenza matematica. In essa vengono riprese le idee di una corrente culturale attiva in quel momento storico secondo la quale la geometria dovesse essere un sistema puramente logico (Vorlesungen über die neuer Geometrie, Pasch, 1882, e I principi della geometria logicamente esposti, Peano, 1889).
Interessandosi all’aspetto logico invece che a quello del contenuto (derivante dall’esperienza), nelle Grundlagen non è più richiesta l’esistenza di una realtà alla quale riferirsi, o meglio di un’unica realtà che costituisca il modello della Geometria. Hilbert accetta, cioè, che il sistema non esprima altro che quello che è previsto dagli assiomi, creando così un primo ed importante esempio di sistema assiomatico inteso in senso moderno: stando a un famoso aneddoto, Hilbert avrebbe sostenuto che i teoremi devono rimanere veri anche se parlano non di punti, rette e piani, ma di “tavoli, sedie e boccali di birra”, sempre che questi oggetti obbediscano agli assiomi.
Potrebbe interessarti anche...
In effetti, la circostanza che gli enunciati di una teoria valessero per ogni altro sistema di enti che si sostituiscano a quelli per i quali la teoria era stata pensata, purché essi soddisfino gli assiomi, era considerato da Hilbert un punto di forza di quella teoria.
Gli assiomi sono, ora, considerati arbitrari, nel senso che non sono giustificati come affermazioni evidentemente vere in qualche dominio della realtà. Questa perdita di contatto con l’esperienza rende necessaria l’adozione di un nuovo criterio di “verità” (o di affidabilità) per gli assiomi, un criterio, cioè, che ne giustifichi l’accettabilità come fondamenta di una teoria. Hilbert individua questo criterio nella compatibilità fra gli assiomi, ovvero, nella loro coerenza: nella teoria non deve essere possibile dimostrare, a partire dagli assiomi, un enunciato scritto nel linguaggio mediante il quale è espressa la teoria ed anche la negazione dell’enunciato stesso.
Le idee di Hilbert nelle Grundlagen hanno avuto conseguenze sull’intera matematica (Hilbert stesso propone anche una assiomatizzazione della teoria dei numeri reali),
sia in quanto esemplificazione del ruolo giocato dai dei sistemi assiomatici sia per il ruolo che hanno avuto nel corso della ricerca sui fondamenti della matematica. Oggi possiamo affermare che l’utilizzo del metodo assiomatico ha permesso la formulazione precisa, e condivisa fra gli studiosi, di teorie in cui non ci sia un riferimento privilegiato, come, ad esempio, la teoria dei gruppi. In questa prospettiva esso si offre come metodo principe al fine di studiare il concetto prescindendo dalle realizzazioni particolari.
Come si è articolata la ricerca sui fondamenti della matematica?
La risposta a questa domanda si intreccia, inevitabilmente, con l’esigenza di assiomatizzazione sorta in seguito alla teorizzazione dell’esistenza di geometrie diverse da quella euclidea, della quale ho detto rispondendo alla domanda precedente. Per grandi linee, e semplicisticamente assai, la ricerca sui fondamenti della matematica si può pensare articolata secondo i punti seguenti:
1) scoperta delle geometrie non euclidee
2) crollo della fiducia nel valore di verità dell’esperienza e dell’intuito, con conseguente esigenza di assiomatizzazione delle teorie matematiche
3) derivazione delle prime teorie assiomatiche (o, secondo una diversa nomenclatura, semiassiomatiche)
4) scoperta di antinomie (paradossi) in dette teorie
5) urgenza di maggiore formalizzazione e passaggio dai sistemi assiomatici ai sistemi formali
6) crescente fiducia nelle “possibilità” dei sistemi formali e programma di Hilbert (anni ’20 del XX secolo)
7) teoremi di Godel e fallimento del programma di Hilbert.
Questo è lo schema (necessariamente e volutamente incompleto) che ho utilizzato nel libro.
Schema incompleto e semplicistico, ribadisco, perché non è facile riassumere il magnifico intreccio di idee, discussioni, conflitti (anche feroci) che hanno avuto luogo nel periodo che va, grosso modo, dagli anni ’20 del XIX secolo agli anni 30 del XX e che sono raggruppati sotto il nome di Ricerca sui fondamenti della matematica.
Ben più dei due capitoli che ho dedicato nel libro all’argomento sarebbero stati necessari (e, invero, molti trattati sono stati dedicati a queste questioni), e, certamente, nel poco spazio di una risposta non posso far altro che limitarmi a tentare di trasmettere al lettore l’idea del fermento intellettuale che permeava quel periodo storico.
Per il suo ruolo non trascurabile nella storia della ricerca sui fondamenti della matematica, è opportuno descrivere brevemente il clima culturale che si respirava in Germania nel corso dell’800 dove la fondazione dell’Università di Berlino nel 1810 (alla quale sono riconducibili molti dei protagonisti della storia che si sta per raccontare) segnava, in qualche modo, l’inizio di un sistema di riforma dell’insegnamento universitario che risentiva delle suggestioni dell’illuminismo tedesco e nella quale i matematici venivano collocati all’interno delle facoltà umanistiche. Ciò, naturalmente, favoriva l’orientamento teorico delle ricerche in ambito matematico e stimolava i matematici all’analisi filosofica delle loro teorie.
In questo contesto, questioni concernenti la natura stessa degli oggetti di studio iniziano a divenire imprescindibili: cos’è una dimostrazione? E, ancora prima, cos’è la matematica? Per quel che concerne la natura della matematica, prendono forma due differenti visioni della stessa: il formalismo che considera la matematica un linguaggio, negando che gli enti oggetto di studio per la matematica abbiano una esistenza propria, indipendente dal linguaggio che li ha generati, e il contenutismo che considera la matematica una scienza, assumendo che il discorso matematico si riferisca ad entità la cui esistenza non è identificabile con gli enti linguistici. Il contenutismo si differenzia successivamente in costruttivismo, secondo il quale la matematica è una scienza costitutiva o anche un’invenzione in quanto gli enti che studia sono un atto costitutivo della mente umana, e platonismo logico, secondo il quale la matematica è una scienza descrittiva o anche una scoperta in quanto gli enti dei quali si occupa hanno una esistenza a priori rispetto alla mente che li studia.
Queste distinzioni erano tutt’altro che mere elucubrazioni filosofiche. Esse potevano avere un impatto significativo sul valore che un matematico assegnava al lavoro di un altro. Un esempio per tutti: un costruttivista non considerava valida una dimostrazione per assurdo di una certa affermazione. Per dimostrare, ad esempio, un’affermazione del tipo “esiste un intero n che soddisfa la proprietà P”, un costruttivista aveva bisogno di individuarlo effettivamente (di costruirlo, appunto) quell’intero e non accettava un ragionamento che mostrasse che se un tale intero non esistesse ciò genererebbe una contraddizione con “verità” già dimostrate nella teoria. Così, il costruttivista Leopold Kronecker (1823-1891) non poteva accettare molto del lavoro di Georg Cantor (1845-1918) al quale dobbiamo la tecnica di dimostrazione per diagonalizzazione (una particolare tecnica di dimostrazione per assurdo). Cantor sentiva così forte la disapprovazione di Kronecker che giunse ad attribuire all’ostracismo di quest’ultimo le difficoltà che incontrava a pubblicare le proprie ricerche.
Nel frattempo, e mentre vedevano la luce le opere che descrivevano le nuove geometrie (non euclidee), l’analisi matematica faceva enormi progressi. Karl Weierstrass, Richard Dedekind e Georg Cantor conseguivano risultati sulla rappresentazione degli irrazionali che permettevano di ricondurre gli enunciati che riguardano grandezze infinitamente piccole in enunciati che esprimono relazioni tra grandezze finite, così raggiungendo l’obiettivo secondo il quale, per usare le parole di Dedekind, “ogni proposizione di algebra o di analisi superiore, per quanto lontana, si lascia esprimere come un teorema sui numeri naturali”. L’analisi veniva così ricondotta all’aritmetica dei numeri naturali. In effetti, Cantor arrivò a elaborare la teoria (ingenua) degli insiemi (della quale è, generalmente, considerato il padre), a partire dal suo Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen del 1874, come risposta a esigenze che si manifestavano con i progressi dell’analisi matematica: ad esempio, la scoperta di funzioni che avevano infiniti punti di eccentricità comportava la necessità di descrivere tali punti e, da qui, quella di introdurre una metodologia per raggruppare oggetti con caratteristiche comuni laddove non sia possibile elencarli uno per uno. Naturalmente, non fu certamente Cantor il primo matematico a sentire questa esigenza, né il primo matematico ad interessarsi agli insiemi. A questo proposito, merita una menzione il lavoro di Dedekind cui si deve l’indicazione di un modo di impostare l’introduzione di concetti matematici in termini insiemistici che alla lunga si sarebbe imposto e generalizzato. Tuttavia, prima di Cantor il concetto di insieme era solo funzionale ad altre teorie. L’impresa di Cantor è stata quella di creare, direttamente e compiutamente, un nuovo nucleo disciplinare.
Nel frattempo, vedeva anche la luce l’opera di un altro eminente matematico tedesco: Gottlob Frege, neoplatonista e kantiano, ma che del pensiero di Kant si proponeva di confutare la concezione della matematica. A questo scopo, l’obiettivo di Frege era dimostrare che le proposizioni aritmetiche sono dimostrabili facendo ricorso alle sole regole del pensiero razionale (ossia, esprimono giudizi analitici e non sintetici, ma questo è un discorso che ci porterebbe troppo lontano). Ciò che si aspettava era che, utilizzando la teoria degli insiemi e una definizione di logica appropriata, si potessero derivare tutti gli insiemi numerici e, in ultima analisi, si potesse fondare l’intera aritmetica. Il suo progetto prendeva le mosse dalla definizione di un linguaggio formale e simbolico che superasse i limiti del linguaggio naturale: un “linguaggio in formule del pensiero puro a imitazione di quello aritmetico” descritto nella sua Ideografia (1879) e con il quale nasceva la nuova logica simbolica. Progetto che portava avanti nei suoi Fondamenti dell’aritmetica (1884), ove sottolineava la volontà di escludere qualunque considerazione “psicologica” e l’intenzione di analizzare il puro contenuto logico dell’aritmetica. A questo proposito, Frege non approvava l’imprecisione della nozione di “insieme” utilizzata da Cantor: in effetti, nella teoria di Cantor il principio di comprensione (secondo il quale ogni proprietà caratterizza un insieme) era considerato ovvio e di esso ci si avvaleva solo implicitamente. Fino a quando Frege non lo codificò nei suoi Principi dell’aritmetica (vol. 1, 1893)…
…Ciò che permise a Bertrand Russell di scoprire la sua antinomia (del tentativo di superare la quale sono figli i Principia Mathematica,1910-13, dello stesso Russel e Alfred Whitehead), che egli comunicò a Frege proprio mentre quest’ultimo era pronto a mandare in stampa il secondo volume dei Principi dell’aritmetica (1903). In effetti, Russell pareva preferire il simbolismo di Peano a quello di Frege (e, infatti, utilizzò nelle sue opere proprio il simbolismo di Peano) da quando lo aveva conosciuto al Convegno di Parigi.
Già, perché mentre Cantor e Frege erano alle prese con le loro teorie, nel frattempo Giuseppe Peano aveva pubblicato Arithmetices Principia nova methodo exposita (opera completamente in latino, 1889) nella quale aveva sviluppato la teoria dei numeri naturali a partire da cinque semplici proprietà (gli assiomi di Peano).
Nel frattempo, altre questioni, correlate al lavoro di Cantor sugli insiemi infiniti, chiedevano attenzione: la dimostrabilità o meno del principio di buon ordinamento e la sua relazione con l’assioma di scelta. Questioni che portarono alla pubblicazione di un articolo (1908) nel quale Ernst Zermelo presentava la prima assiomatizzazione della teoria degli insiemi (completata, qualche anno più tardi, da Adolf Fraenkel).
Comunque sia, nonostante Zermelo fosse momentaneamente riuscito ad arginarli, i paradossi collegati alla teoria degli insiemi (altri ne erano stati individuati, oltre a quello di Russell) dovevano essere affrontati. In ultima analisi, l’esigenza comunemente sentita era quella di dimostrare la coerenza dei sistemi assiomatici proposti. Solo da questa dimostrazione sarebbe conseguito che gli enunciati matematici sono realmente verità incontestabili, ristabilendo la reputazione della “matematica come modello della scienza più rigorosa” (Hilbert, Pensiero Assiomatico, 1917). E, a tal proposito, Hilbert abbozza nel 1904 la sua prima proposta di una nuova impostazione dei fondamenti della teoria dei numeri basata sul metodo assiomatico ma anche su un ripensamento della logica di base, da costruirsi in una con l’aritmetica elementare.
In effetti, come è stato detto nel corso della discussione sui sistemi assiomatici, Hilbert si era occupato di questioni di coerenza in relazione alla geometria; in particolare egli aveva mostrato come eventuali contraddizioni derivanti dagli assiomi della sua geometria sarebbero riconducibili a contraddizioni nell’aritmetica dei numeri reali. In tal modo, Hilbert aveva ricondotto la non contraddittorietà della geometria a quella dell’aritmetica dei numeri reali. D’altra parte, in conseguenza dei già citati risultati di Weierstrass, Dedekind e Cantor, anche la questione della non-contraddittorietà del sistema di assiomi per i numeri reali poteva essere ricondotta, mediante l’uso di concetti insiemistici, all’analoga questione per i numeri naturali. Nella visione di Hilbert, solo quando si ha a che fare con gli assiomi dei numeri interi e con la fondazione della teoria degli insiemi “è chiaro che non è praticabile questa via di riconduzione ad un altro più particolare campo conoscitivo, poiché oltre alla logica non c’è proprio più alcuna disciplina alla quale si potrebbe far ricorso”.
Si stava, così, delineando quello che sarà ricordato come il programma di Hilbert: la formalizzazione dell’intera matematica mediante un sistema costituito di un insieme finito di assiomi e di un sistema (finito) di regole deduttive. Dall’osservazione che proprio la necessità di definizione dei numeri naturali in termini di concetti astratti aveva condotto l’approccio di Frege a incappare nel paradosso di Russell, Hilbert teorizzò che la strada per liberarsi definitivamente dai paradossi, e per dimostrare la coerenza di sistemi fondanti per l’aritmetica passasse per una formalizzazione estrema che svuotava di ogni significato i simboli utilizzati: così, ad esempio, i numeri naturali non erano più altro che i segni I, II, III, IIII, … che li rappresentavano. E anche gli enunciati, così come le dimostrazioni, diventavano, nella visione di Hilbert, pure sequenze di simboli: “Tutte le proposizioni che costituiscono la matematica sono convertite in formule, così che la matematica vera e propria diventa un inventario di formule” (I fondamenti della matematica, 1927).
Era convinto, Hilbert, che il suo approccio avrebbe permesso di fondare coerentemente e compiutamente la matematica. Che “In der Mathematik gibt es kein Ignorabimus” (“in matematica non c’è alcun ignoreremo”) e che, come disse nel corso dell’intervento che tenne, nel 1930 a Konigsberg, ad un convegno organizzato per il suo pensionamento, “Dobbiamo sapere, sapremo!”. E poi …
… E poi arrivò Godel. Kurt Godel. Che, invece, dimostrò che sapere tutto, no: non era proprio possibile.
Cosa stabilisce la Teoria della Complessità Computazionale?
Facile: la Teoria della Complessità Computazionale si occupa di stabilire la quantità di risorse computazionali che occorrono per risolvere un problema e di classificare i problemi risolvibili in teoricamente risolvibili e effettivamente risolvibili! Tuttavia questa, pur intuitiva, dicitura è parecchio imprecisa. Talmente imprecisa, che quasi nulla chiarisce della questione (e non è un caso che ben tre capitoli mi sono occorsi nel libro per arrivare a parlarne). Tanto per cominciare, occorre chiarire cosa si intende affermando che un problema è, o non è, risolvibile.
Allora, tutto cominciò con Hilbert, il grande matematico che tanta parte ha avuto in quel che si è detto alla risposta precedente. Nell’ambito del suo programma, Hilbert aveva posto l’Entscheidungsproblem: trovare un metodo che, data una formula espressa nel sistema formale della logica del primo ordine, determini in un numero finito di passi ben definiti ed effettivi, se essa sia o non sia un enunciato deducibile all’interno del sistema formale. In altri termini, ciò che Hilbert cercava era un procedimento che, presa una qualsiasi una formula della logica del primo ordine, fosse in grado di concludere, dopo aver eseguito un numero finito di operazioni (ben definite ed effettive): “quella formula è derivabile nel sistema” oppure “quella formula non è derivabile nel sistema”. Qualunque formula venisse sottoposta al suo giudizio, il procedimento doveva essere in grado di prendere una decisione.
Per affrontare l’Entscheidungsproblem occorreva, per prima cosa, chiarire cosa fosse un procedimento e cosa una operazione ben definita ed effettiva. Semplicisticamente parlando, un procedimento è una lista di istruzioni che assomiglia, un poco, ad una ricetta scritta su un libro di cucina: l’indicazione delle azioni che devono essere eseguite per portare a termine un compito insieme con la specifica dell’ordine esatto nel quale devono essere eseguite. Nei primi anni della nostra educazione scolastica, ad esempio, ci è stato insegnato il procedimento che permette di eseguire l’addizione fra due numeri interi. E, naturalmente, il procedimento che ci è stato insegnato permette di addizionare qualunque coppia di interi – non soltanto 12 e 28, per dire. Non soltanto numeri con un massimo numero di cifre. Ma ogni coppia di interi. E questa caratteristica di generalità è imprescindibile in ogni procedimento di calcolo.
Un modello di calcolo è un linguaggio che permette di descrivere procedimenti: esso consiste in una serie di regole che specificano come sono strutturate le istruzioni (la loro sintassi), in quale ordine devono essere eseguite e, infine, l’insieme di azioni che possono essere indicate all’interno delle istruzioni. Tale insieme, che ha dimensioni limitate, è l’insieme delle operazioni elementari: le operazioni ben definite ed effettive di cui si diceva sopra. E, naturalmente, per poter affrontare l’Entscheidungsproblem, era prima di tutto necessario definire un modello di calcolo nel quale sarebbe stato descritto il procedimento agognato da Hilbert.
Pressoché contemporaneamente, Alonzo Church e Alan Turing definirono due diversi modelli di calcolo (rispettivamente, il lambda-calcolo e la Macchina di Turing) e dimostrarono l’esistenza di formule delle quali nessun procedimento descritto in accordo ai modelli che avevano definito poteva concludere se erano o meno derivabili nel sistema. E, sempre pressoché contemporaneamente, dimostrarono anche che i loro due modelli erano equivalenti: ossia, semplificando, che tutti i calcoli che potevano essere eseguiti in uno dei due modelli potevano essere eseguiti anche nell’altro. I due studiosi elaborarono anche una congettura, la tesi di Church-Turing, secondo la quale tutti i modelli di calcolo sono equivalenti (sempre semplificando, perché, naturalmente, cosa si intenda precisamente con modello di calcolo non è stato chiarito in questa sede). E, in effetti, tutti i modelli di calcolo sviluppati da allora in poi sono stati dimostrati essere equivalenti fra loro.
Concentriamoci, ora, su Turing e la sua Macchina. Intanto, un procedimento descritto in accordo al modello Macchina di Turing (‘M’ maiuscola) prende il nome di macchina di Turing (‘m’ minuscola). Poi, per dimostrare l’esistenza di una formula descritta nel linguaggio della logica del primo ordine della quale nessuna macchina di Turing poteva concludere se fosse o meno derivabile nel sistema formale, Turing definì un particolare insieme D, che conteneva sequenze di ‘0’ e ‘1’ costruite in base ad un particolare insieme di regole, e mostrò che non esiste alcuna macchina di Turing che riesca a decidere per ogni sequenza x di ‘0’ e ‘1’ se x appartiene a D oppure no. Questo significa che: comunque si provi a scrivere un procedimento (in accordo al modello Macchina di Turing) per decidere l’appartenenza di sequenze di ‘0’ e ‘1’ all’insieme D, prima o poi si incapperà in una sequenza che il procedimento non sarà in grado di collocare in D né fuori di D.
Come ciò si colleghi con l’Entscheidungsproblem esula dagli obiettivi di questa discussione (ed è, invece, descritto nel libro). Quello che ci interessa è che Turing ha dimostrato che non esiste alcuna macchina di Turing (ossia, alcun procedimento progettato in accordo al modello Macchina di Turing) che sa rispondere alla domanda “data la sequenza x costituita di ‘0’ e ‘1’, x appartiene all’insieme D?” per tutti gli x possibili. Ossia, non potendo rispettare la caratteristica di generalità, nessuna macchina di Turing risolve il problema di decidere dell’appartenenza a D di sequenze costituite di ‘0’ e ‘1’. Poi, in virtù della tesi di Church-Turing, da ciò segue che nessun procedimento progettato in accordo a qualunque modello di calcolo (cui d’ora in poi ci riferiremo come ad un algoritmo) risolve il problema di decidere dell’appartenenza a D di sequenza costituita di ‘0’ e ‘1’.
Poiché l’insieme D è costituito di sequenze di caratteri (‘0’ e ‘1’), ossia, di parole (binarie), ci si riferisce ad esso come ad un linguaggio. E, siccome si è mostrato che nessun algoritmo è in grado di decidere l’appartenenza a D, esso è un linguaggio indecidibile. Naturalmente, qualunque insieme, scegliendo opportunamente una codifica dei suoi elementi, può essere descritto come un linguaggio sui caratteri ‘0’ e ‘1’. E così, la Teoria della Calcolabilità di occupa (sempre semplificando assai) di classificare i linguaggi in decidibili e indecidibili.
Ora, se un linguaggio L è decidibile allora esiste un algoritmo in grado di rispondere sempre alla domanda “x appartiene a L?” – sempre, ossia, qualunque sia la parola x. D’altra parte, per qualche parola y, l’algoritmo che decide L potrebbe dover eseguire un numero talmente elevato di operazioni al fine di decidere se y appartiene a L che un’intera vita umana non sarebbe sufficiente per ottenere una risposta. In tal caso, sapere che il linguaggio L è decidibile non sarebbe particolarmente utile all’atto pratico.
In risposta a questa osservazione nasce la Teoria della Complessità Computazionale. Il punto di partenza è quello di associare una misura a ciascuna computazione di una macchina di Turing, dove, in generale, una computazione di un algoritmo è l’esecuzione di quell’algoritmo su certi dati: se AL è l’algoritmo che decide l’appartenenza al linguaggio L, quando chiediamo ad AL se la parola 01110 appartiene a L eseguiamo la computazione AL(01110). Una misura di complessità è una funzione che associa a una computazione di una macchina di Turing la quantità di risorse di un certo tipo utilizzate durante quella computazione. Così, la misura di complessità tempo associa ad una computazione di una macchina di Turing il numero di operazioni che essa esegue. Anche se sono state definite svariate misure di complessità, la discussione che segue focalizzerà solo sulla misura tempo.
A questo punto, data una certa macchina di Turing T (ossia, un algoritmo espresso nel modello di calcolo Macchina di Turing) viene definita la complessità temporale di T come una funzione fT : ℕ → ℕ definita come di seguito descritto. Per ogni intero n, si considerano tutte le computazioni T(x) in cui x è una parola di n caratteri e si sceglie quella che esegue il massimo numero di operazioni: fT(n) è il numero di operazioni eseguite da quella computazione. In questo modo, la complessità di una macchina di Turing viene espressa come numero di operazioni che essa, per ciascun intero n, esegue nel caso peggiore.
E, infine (infine!) diciamo che un linguaggio ha complessità temporale f(n) se esiste una macchina di Turing che lo decide che ha complessità f(n).
Finalmente, possiamo dire che un linguaggio decidibile è trattabile computazionalmente (ovvero, è decidibile all’atto pratico) se la sua complessità temporale è un polinomio: l’insieme dei linguaggi trattabili (decidibili in tempo polinomiale) costituisce la classe P. Perché siano state scelte funzioni polinomiali come soglia di trattabilità è descritto nel capitolo 6 del libro – a partire dalla storia della torre di Hanoi. In questa sede riesco solo a dire, brevemente (e, al solito, semplificando), che, poiché la crescita di una funzione più che polinomiale al crescere del suo argomento è stupefacentemente più veloce di quella di una funzione polinomiale, il numero di operazioni richiesto da una macchina di Turing con complessità più che polinomiale sarebbe (nel caso peggiore) irragionevolmente lungo già per decidere parole costituite da “pochi” caratteri.
Vale la pena osservare che, mentre per dimostrare che un linguaggio è in P è sufficiente individuare un algoritmo avente complessità polinomiale che lo decide, per dimostrare che un linguaggio non appartiene a P occorre mostrare che ogni algoritmo che lo decide esegue per qualche parola sulla quale deve prendere una decisione un numero di operazioni più che polinomiale nella lunghezza di quella parola. Compito, quest’ultimo, senz’alcun dubbio di gran lunga più arduo. Pertanto, esiste una moltitudine di linguaggi per i quali non è stato trovato alcun algoritmo polinomiale che li decide né, d’altro canto, si è riusciti a dimostrare che un siffatto algoritmo non esiste. Non affrontiamo, però, in questa sede la gestione di tale moltitudine di linguaggi operata dalla Teoria della Complessità Computazionale.
Resta da collegare questo (pur magnifico) impianto teorico, fatto di macchine di Turing & linguaggi, a quel con cui abbiamo a che fare nella vita di tutti i giorni: ovvero, algoritmi e problemi. Il primo passo è facile: tutti i modelli di calcolo definiti sino ad ora (inclusi, dunque, i linguaggi di programmazione) sono polinomialmente correlati al modello di calcolo Macchina di Turing. Questo significa che esiste una macchina di Turing che decide un linguaggio in tempo polinomiale se e soltanto se esiste un algoritmo scritto in accordo ad ogni altro modello di calcolo noto (ad esempio, in C, o in Python, …) che decide quel linguaggio in tempo polinomiale. E, analogamente alla Tesi di Church-Turing nella Teoria della Calcolabilità, la Teoria della Complessità Computazionale ha la sua Tesi di Cobhan: tutti i modelli di calcolo che possono essere implementati (ossia, realizzati in pratica) sono fra loro polinomialmente correlati.
Ora, la seconda questione: il passaggio da linguaggi a problemi. Intanto, è possibile individuare una categoria di problemi che possono essere descritti in forma di linguaggi. Si tratta dei problemi decisionali, quelli nei quali viene chiesto di decidere se una certa proprietà è vera: ad esempio “esiste un percorso da A a B lungo non più di tot km.?”. Un problema viene, in genere descritto, mediante un insieme di parametri, ossia, di entità lasciate indeterminate (A, B e tot nell’esempio). Ogniqualvolta si assegna un “valore” a ciascuno di questi parametri si ottiene un’istanza del problema: “esiste un percorso da Roma a Firenze lungo non più di 350 km.?”. Il linguaggio associato ad un problema decisionale è l’insieme delle istanze del problema per le quali la proprietà è vera. Perciò, diciamo che un problema decisionale è trattabile computazionalmente se il linguaggio corrispondente appartiene a P.
Ma i problemi di decisione sono soltanto una particolare categoria di problemi (e di interesse pratico probabilmente anche limitato…). Seppure si tratti di una questione un po’ delicata (che non può essere trattata in questa sede), è, in effetti, spesso possibile utilizzare le conoscenze circa i problemi di decisione anche per capire quanto “costa”, in termini di risorse computazionali, risolvere un problema nel quale viene richiesto di calcolare qualcosa. Ad esempio, al problema “calcola il percorso più breve da A a B”, o anche al problema “calcola un percorso da A a B lungo non più di tot km. (nel caso esso esista)”, possiamo far corrispondere il problema decisionale “esiste un percorso da A a B lungo non più di tot km.?”. Ovviamente, in questo caso, se riusciamo a calcolare il percorso più breve o un percorso di lunghezza non superiore a un valore dato in tempo polinomiale, allora riusciamo anche a decidere il problema decisionale in tempo polinomiale. E anche il viceversa è vero (sebbene mostrarlo sia leggermente più complicato).
Ed ecco perché, allora, possiamo dire che la Teoria della Complessità Computazionale si occupa di stabilire la quantità di risorse computazionali che occorrono per risolvere un problema e di classificare i problemi risolvibili in problemi teoricamente risolvibili e problemi effettivamente risolvibili. Facile!
Quali conseguenze avrebbe la dimostrazione della congettura P±NP?
In effetti, la tendenza generale, nella comunità scientifica, è quella di ritenere vera la congettura P ≠ NP. Conseguentemente, la ricerca, fin dall’inizio, si è orientata verso direzioni che permettessero di convivere con questo fatto: se P è diverso da NP allora non esistono algoritmi polinomiali che “risolvano” problemi NP-completi, e dunque, facendo di necessità virtù, è necessario trovare (inventare, definire, progettare) modi alternativi per trattare questi problemi. E questo è quanto ho (brevemente) raccontato nell’ultimo capitolo del mio libro: sono state introdotte nuove misure della complessità di un algoritmo (considerando il caso medio anziché il caso peggiore), si sono progettati algoritmi che molto spesso (o quasi sempre) sono trattabili o che molto spesso (o quasi sempre) trovano la soluzione corretta, sbagliando, invece, raramente (o quasi mai). Sono stati definiti gli algoritmi di approssimazione. Insomma, sono stati inventati significati diversi da associare al concetto “risolvere un problema”. Cosa accadrebbe, dunque, se si dimostrasse che P ≠ NP? Poco o niente di nuovo, in effetti.
Probabilmente, conseguenze più rilevanti deriverebbero dall’eventualità che venisse dimostrato P = NP. Di primo impatto, si potrebbe pensare che sarebbe meraviglioso sapere che tutti i problemi che popolano NP (che sono problemi che hanno grande rilevanza pratica, va sottolineato) possono essere risolti da algoritmi polinomiali – e quindi, efficienti, veloci, davvero utilizzabili insomma! Tuttavia… Tuttavia, sapere che esiste la possibilità di risolverli in tempo polinomiale non vuol dire saperli risolvere in tempo polinomiale. Questo significa che, per essere significativa all’atto pratico, la dimostrazione che P = NP dovrebbe essere costruttiva, ossia, dovrebbe mostrare come dall’informazione che un certo problema è in NP si possa dedurre un algoritmo polinomiale che risolva quel problema. E la teoria della NP-completezza è stata “inventata” proprio per percorrere questa strada: se esistesse (se si costruisse) un algoritmo polinomiale per risolvere un problema NP-completo allora quell’algoritmo, unito alla costruzione utilizzata nella prova del teorema di Cook-Levin (e a qualche altra questioncina), permetterebbe di costruire un algoritmo polinomiale per risolvere qualsiasi altro problema in NP – e questo è discusso ampiamente nel capitolo 8 del libro.
Se, quindi, si riuscisse a costruire un algoritmo polinomiale per risolvere un problema NP-completo, saremmo tutti contenti. Beh, insomma, non del tutto. Perché c’è anche un rovescio della medaglia. A questo proposito, si narra che se si dimostrasse che P = NP allora verrebbero messi in crisi i sistemi crittografici attualmente in uso. Cerchiamo, dunque, di comprendere il significato e la portata di quest’affermazione. Ci sono Alice e Bob, che vivono distanti e che hanno bisogno di comunicare privatamente. Più precisamente, Alice deve inviare informazioni confidenziali a Bob (che da Bob devono essere comprese) ed essi non desiderano che qualcuno che riesca a intercettare i messaggi inviati da Alice riesca a comprenderne il significato. Perciò, hanno bisogno di due procedimenti: E, che codifica in qualche linguaggio segreto i messaggi che Alice manda a Bob, e D che decodifica i messaggi inviati da Alice che Bob riceve. Naturalmente, se x è un messaggio che Alice vuole inviare a Bob, deve accadere che D(E(x)) = x (altrimenti, Bob non sarebbe in grado di comprendere ciò che Alice intendeva comunicargli). Inoltre, Alice e Bob vorrebbero che, qualora Charlie riesca ad intercettare E(x), sia per lui impossibile risalire a x non conoscendo D. Chiariamo subito: è impossibile che ciò sia impossibile. L’unica possibilità per Alice e Bob è scegliere E in modo tale che risalire a x da E(x) senza conoscere D richieda una quantità irragionevole di tempo, ossia, sia computazionalmente intrattabile. Ma, in realtà, neanche questo è possibile allo stato attuale delle nostre conoscenze. Infatti, anche se di problemi computazionalmente intrattabili, ossia, che per certo non appartengono a P, se ne conoscono (sebbene in numero piuttosto limitato), essi non si prestano ad essere utilizzati in questa situazione. Perché è stato dimostrato che, se nel processo di codifica / decodifica non si vuole perdere informazione, ossia, sostanzialmente, se si vuole che Bob sia in grado di ricostruire esattamente il messaggio x inviato da Alice, allora il problema di risalire a x conoscendo E ma non D deve appartenere a NP. Ecco perché, se si individuasse un algoritmo polinomiale che risolvesse un problema NP-completo, questo metterebbe in crisi i sistemi crittografici attualmente in uso: a partire da quell’algoritmo si riuscirebbe a costruire un algoritmo polinomiale che permetterebbe di risalire a x conoscendo E ma non D. Tuttavia…
Tuttavia, la Teoria della Complessità Computazionale studia la complessità degli algoritmi nel caso peggiore. Caso peggiore che potrebbe presentarsi molto raramente. Così, per esempio, potremmo avere un algoritmo di complessità esponenziale, diciamo 2n, nel caso peggiore; ma, per ogni intero n, c’è un solo input di n caratteri che richiede quella complessità elevata, mentre per tutti gli altri input di n caratteri quell’algoritmo opera in tempo 2n. E potremmo avere anche un altro algoritmo di complessità polinomiale che risolve lo stesso problema e che, per tutti gli input di n caratteri, opera in tempo 256n10. Certamente, in linea teorica il secondo algoritmo è preferibile al primo. Tuttavia, nella stragrande maggioranza dei casi sarà il primo algoritmo, quello a complessità esponenziale, a trovare per primo la risposta. E, magari, per le istanze veramente interessanti l’algoritmo davvero intrattabile sarà il secondo.
E poi… E poi, c’è il mondo che sta cambiando. Siamo nell’era dei Big Data. Reti (di svariate forme e sostanze) costituite da un numero elevatissimo di entità che generano quantità inimmaginabili di dati che devono essere elaborati per fini commerciali, medici, legali o, semplicemente, per migliorare le prestazioni delle reti stesse. L’esigenza di analizzare, estrapolare, mettere in relazione (e via discorrendo) enormi moli di dati eterogenei e di fornire risposte a problemi in tempo reale rende di fatto inutilizzabili algoritmi la cui complessità è più che lineare. In questo scenario, dunque, la soglia di intrattabilità deve essere collocata ben al di sotto di quella individuata dalla classe P, così che la relazione fra P e NP sembra perdere rilevanza in questo contesto. Tuttavia…
Tuttavia, anche i progressi tecnologici corrono velocemente. Così, magari, in un futuro neanche troppo lontano, riusciremo a costruire processori ultra-veloci. Più veloci degli attuali di qualche ordine di grandezza. E, grazie a loro, riusciremo ad eseguire in tempi ragionevoli anche algoritmi ben più che lineari su istanze molto, molto grandi (ovvero, per valori di n molto, molto elevati). Si potrebbe obiettare che, però, questi nuovi processori eseguirebbero molto più velocemente anche gli algoritmi che hanno complessità esponenziale. E questo è vero, naturalmente. Ma, mentre l’uso di questi (futuristici) processori risulterebbe in un’accelerazione sensibile (nel senso di “rilevabile attraverso i sensi”) nel caso di un algoritmo polinomiale, essa sarebbe pressoché irrilevante (e impercettibile) nel caso di un algoritmo esponenziale. Ad esempio, consideriamo
- un algoritmo A di complessità n10 (che è una gran bella complessità!) e sia x un’istanza di dimensione n = 100000 sulla quale quell’algoritmo esegue proprio 10000010=1050 (ossia, 1 seguito da 50 zeri) operazioni
- e un algoritmo B di complessità 2n che sulla stessa istanza x di operazioni ne esegue 2100000 1010000 (ossia, 1 seguito da 10000 zeri!).
Se venisse progettato un processore 1040 volte più veloce dei processori attuali (gran bella accelerazione!), che impiegano ordine di un miliardesimo di secondo (ovvero, 10-9 secondi) per eseguire una singola operazione, allora
- la computazione A(x) su questo nuovo (futuristico) computer richiederebbe ordine di 10501091040 = 10 secondi contro i 1050109 = 1041 secondi > 1033 anni che essa richiede sui computer attuali e la differenza sarebbe ben sensibile (!),
- la computazione B(x) sul nuovo (futuristico) computer richiederebbe 10100001091040 = 109951 secondi contro i 109991 secondi che essa richiede sui computer attuali, ossia, in entrambi i casi richiederebbe un tale numero di anni che la differenza sarebbe impossibile da percepire (!).
Controversa, dunque, la questione della portata pratica dell’eventuale dimostrazione P = NP…
D’altro canto, neanche a dirlo, risolvere, in un senso o nell’altro, la congettura P ≠ NP avrebbe un impatto non trascurabile nel mondo teorico, ma, prima di entrare nel merito di questo diverso punto di vista, è necessario chiarire una questione che non è stata trattata nel corso della risposta alla domanda precedente. Come abbiamo già accennato, sono pochi i problemi per i quali è stata dimostrata la non appartenenza a P mentre, invece, esiste una moltitudine di problemi per i quali non è stato trovato alcun “algoritmo risolvente” che opera in tempo polinomiale né, d’altro canto, si è riusciti a dimostrare che un siffatto algoritmo non esiste. Nel tentativo di collocarli al di qua o al di là della barriera della risolvibilità polinomiale, la Teoria della Complessità Computazionale ha definito, sostanzialmente, una gerarchia di “modelli di calcolo teorici” ottenuti a partire dal modello Macchina di Turing e aggiungendo ad esso istruzioni via via più potenti – tanto potenti che, al momento, i modelli così introdotti non sembrano poter corrispondere a calcolatori effettivamente realizzabili né sembrano soddisfare la tesi Cobhan. Corrispondentemente a ciascun “modello di calcolo teorico” è stata definita una classe di complessità, ossia, l’insieme dei problemi che possono essere risolti da un “algoritmo” polinomiale scritto in accordo alle regole di quel “modello di calcolo teorico”. Alla base della gerarchia si trova la classe P (l’unica corrispondente ad un modello di calcolo effettivo), e la classe immediatamente successiva a P è la classe NP. Possiamo, quindi, dire che, fra i problemi che non riusciamo a classificare, i problemi che popolano NP sono quelli “risolti” da un “algoritmo” scritto in accordo al “modello di calcolo” più simile alla Macchina di Turing (e, quindi, che meno si discosta da un algoritmo vero e proprio). Per dirla facile, i problemi in NP sono i problemi “meno complessi” fra i problemi che non riusciamo a classificare né in P né fuori da P.
Ebbene, se si dimostrasse che P è uguale a NP, tutta questa gerarchia di classi collasserebbe. Ciascuna classe, per quanto definita sulla base di un modello di calcolo capace di eseguire “in un solo passo” operazioni apparentemente molto (ma molto molto) più complesse di quelle che, “in un solo passo”, possono essere eseguite sugli odierni calcolatori, ebbene, ciascuna di queste classi sarebbe parte della classe P. Ovvero, tutti i problemi contenuti in ciascuna di queste classi sarebbero risolvibili da algoritmi che possono essere eseguiti su calcolatori reali in tempo polinomiale.
Di contro, se si dimostrasse che P è diverso da NP (confermando la congettura), questo significherebbe che il modello Macchina di Turing Non Deterministica, ossia, la generalizzazione del modello Macchina di Turing, sul quale è basata la classe NP, è strettamente più potente (nel senso della “velocità” di calcolo) del modello deterministico sul quale sono basati gli odierni calcolatori. Ma questo non sarebbe sufficiente per capire se le altre classi della gerarchia sono distinte o meno da P. Dalla risoluzione di una congettura, ne resterebbero, dunque, aperte un buon numero di altre.
E, infine, il mio personale punto di vista. L’importanza della questione “P ≠ NP?” non è tanto nella risposta che (forse, prima o poi) ad essa si riuscirà a fornire quanto, piuttosto, nella ricerca di quella risposta. Nelle innumerevoli direzioni di ricerca, nel “fiume in piena”, che da essa hanno avuto origine. Perché, come si dice nelle righe di presentazione del mio libro, “quando provi a risolvere un problema, non lo sai dove ti porteranno i tuoi tentativi, e magari arriverai a percorrere sentieri insospettabili”. È così che, ad esempio, Cantor, cercando una definizione per i numeri reali, ha trovato la teoria degli insiemi. E, sempre così, dal (fallimento del) programma di Hilbert siamo arrivati al problema da un milione di dollari.
Miriam Di Ianni ha conseguito la laurea in Matematica, presso l’Università degli Studi di Roma “La Sapienza” e, successivamente, presso la stessa Università, il Dottorato di Ricerca in Informatica. Attualmente, è Professore Associato presso l’Università degli Studi di Roma “Tor Vergata”, dove tiene i corsi di Fondamenti di Informatica, per il corso di laurea triennale in Informatica, e di Analisi di Reti, per il corso di laurea Magistrale in Informatica. Autrice di numerose pubblicazioni scientifiche (componente integrante della docenza universitaria) e del materiale didattico dei corsi tenuti, Il sentiero dei problemi impossibili è la prima opera a carattere divulgativo della quale è autrice.
