DENTRO LA SCA
DENTRO LA SCATOLATOLA
Rubrica a cura di
Fabio A. Schreiber
Il Consiglio Scientifico della rivista ha pensato di attuare un’iniziativa culturalmente utile presentando in ogni numero di Mondo Digitale un argomento fondante per l’Informatica e le sue applicazioni; in tal modo, anche il lettore curioso, ma frettoloso, potrà rendersi conto di che cosa sta “dentro la scatola”. È infatti diffusa la sensazione che lo sviluppo formidabile assunto dal settore e di conseguenza il grande numero di persone di diverse estrazioni culturali che - a vario titolo - si occupano dei calcolatori elettronici e del loro mondo, abbiano nascosto dietro una cortina di nebbia i concetti basilari che lo hanno reso possibile.
Il tema scelto per il 2004 è stato: “Perché gli anglofoni lo chiamano computer, ovvero: in- troduzione alle aritmetiche digitali”. Per il 2005 il filo conduttore della serie sarà: “Ma ce la farà veramente?, ovvero: introduzione alla complessità computazionale e alla indeci- dibilità” e il suo intento è di guidare il lettore attraverso gli argomenti fondanti dell’Informatica e al- le loro implicazioni pratiche e filosofiche. La realizzazione degli articoli è affidata ad autori che uni- scono una grande autorevolezza scientifica e professionale a una notevole capacità divulgativa.
Potenza e limiti del calcolo automatico:
problemi intrattabili
1. INTRODUZIONE
Questo è l’ultimo articolo di una serie di quattro dedicata agli aspetti più concettua- li e teorici dell’informatica. I primi due articoli si sono focalizzati sulla nozione di algoritmo come formalizzazione della nozione di calcolo auto- matico, e sulla possibilità di risolvere problemi in modo algoritmico. Il terzo, che costituisce la prima parte del presente, ha introdotto il concet- to di complessità computazionale di un algorit- mo, intesa come una misura, indipendente dal calcolatore e dal linguaggio di programmazione utilizzato, del tempo di calcolo e dello spazio di memoria necessari per eseguire l’algoritmo.
Questo articolo si sofferma sulle conseguenze più profonde dei concetti di complessità compu- tazionale, con importanti ricadute pratiche in domini come la sicurezza del commercio elettro- nico o l’ottimizzazione delle risorse.
2. LA TEORIA DELLA COMPLESSITÀ COMPUTAZIONALE
Un problema computazionale è un problema che ammette una soluzione algoritmica, ossia una soluzione che può essere calcolata, almeno
in teoria, da un computer opportunamente pro- grammato. L’algoritmo però deve essere ragio- nevolmente efficiente, ossia impiegare un tem- po non eccessivo per calcolare la risposta, e non deve aver bisogno di una quantità di memoria maggiore rispetto a quella disponibile.
In questo articolo ci soffermiamo sulla cosiddet- ta Teoria della Complessità Computazionale (TCC), il cui oggetto di studio non è tanto l’effi- cienza di un singolo algoritmo, ma l’ammontare delle risorse computazionali (come tempo di esecuzione, spazio di memoria, dimensione dei circuiti) necessarie per risolvere problemi com- putazionali. La TCC è indipendente dagli algorit- mi effettivamente utilizzati per risolvere i proble- mi, ma si propone di determinare la complessità dei migliori algoritmi possibili (spesso anche senza conoscerli). La TCC è in larga misura indi- pendente persino dal modello computazionale adottato (macchine di Turing, macchine RAM, calcolatori paralleli,...), a patto che questo sia fi- sicamente realizzabile.
La TCC costituisce uno dei maggiori successi scientifici degli ultimi quaranta anni, con risulta- ti di portata molto generale. I suoi modelli com- putazionali astratti classificano le migliaia di Pierluigi San Pietro
1 0
0 0 1
problemi computazionali del mondo reale in poche classi di equivalenza, all’interno delle quali i problemi ammettono soluzioni algorit- miche pressappoco della stessa efficienza.
Quindi, studiando un nuovo problema X, è suf- ficiente mostrare che X ricade in una certa clas- se per avere subito un’idea approssimativa del- la complessità computazionale delle sue solu- zioni, anche senza avere ancora sviluppato di- rettamente alcun algoritmo per X. Inoltre, nota la classe di complessità, la progettazione di un algoritmo è spesso molto facilitata, in quanto esistono molte tecniche che aiutano nello svi- luppo di algoritmi efficienti per i problemi di una stessa classe.
Il contributo più importante della TCC consiste forse nell’avere riconosciuto che esistono pro- blemi di grande rilevanza pratica, la cui risolu- zione esatta è (o, spesso, sembra) intrinseca- mente difficile qualunque sia lo strumento di calcolo utilizzato, e che si possono quindi risol- vere solo in casi particolari.
3. UN SEMPLICE ESEMPIO
Un commesso viaggiatore deve visitare in auto- mobile N città. Desidera stabilire se esiste un percorso che visita una sola volta tutte le città e la cui lunghezza complessiva sia inferiore a un valore K, oltre il quale la sua attività non è più conveniente. A tale fine, ha a disposizione una cartina stradale, da cui si ricava facilmente l’e- sistenza e la lunghezza delle strade dirette di collegamento da una città a un’altra.
Si rivolge quindi a un programmatore, grande esperto di sistemi e linguaggi informatici, ma assai digiuno di TCC, che prepara il seguente algoritmo:
1.disponi le N città in una permutazione qual- siasi C1, C2, …, CN;
2.se esiste un percorso che parte da C1passa per C2, ..., per arrivare infine a CN, calcolane la lunghezza complessiva L; se L è minore di K, stampa il percorso e termina con successo;
3.se non ci sono più permutazioni disponibili, termina con un fallimento, altrimenti scegli una nuova permutazione e riparti da 2.
Supponiamo di dovere visitare 4 città, chiama- te A, B, C e D. L’algoritmo per esempio può cal- colare dapprima la lunghezza del percorso A B C D (cioè il percorso che parte da A, poi passa per B, poi per C e infine per D). Se vi sono stra-
de di collegamento fra A e B, B e C, C e D, l’al- goritmo calcola la lunghezza complessiva del percorso e, se questa è minore di K, termina l’esecuzione. Altrimenti prova un’altra se- quenza, per esempio A C B D, e così via fino a trovare una soluzione o esaurire tutti i percor- si possibili.
Quanto tempo ci vuole per ottenere una ri- sposta?
Il caso migliore (il più favorevole per l’algorit- mo) è quello in cui proprio il primo percorso scelto ha lunghezza inferiore a K. Il caso peg- giore, invece, corrisponde alla situazione in cui si provano tutte le sequenze del tipo A B C D, A B D C, A C B D, ..., per concludere magari che nessuna ha lunghezza inferiore a K. Cal- coliamo il numero di queste sequenze (o per- mutazioni di N elementi). La città da visitare per prima può essere una qualunque delle quattro, mentre in seconda posizione ci può essere una qualunque delle tre rimanenti, se- guita in terza posizione da una qualunque delle due ancora da visitare, seguita infine dall’ultima città non ancora visitata. Ci sono quindi 4 · 3 · 2 · 1 = 24 possibili percorsi, che anche un computer scalcinato può enumera- re in un batter d’occhio.
Cosa succede all’aumentare del numero delle città?
Se al posto di 4 città ce ne fossero 10? O 30?
Il ragionamento precedente può essere gene- ralizzato alla visita di N città, ricavando che nel caso peggiore l’algoritmo deve verificare N! = N (N – 1) (N – 2)...1 possibili percorsi. Per visitare 10 città, l’algoritmo dovrebbe provare 10! permutazioni, cioè quasi quattro milioni di casi: questo richiederebbe più tempo, ma ba- sterebbe acquistare un calcolatore più poten- te per cavarsela in una manciata di secondi. E per visitare 30 città? È sufficiente comprare un calcolatore ancora più potente?
Le permutazioni da provare sono 30!, circa 2,6 · 1032. Se un’antica specie aliena avesse costruito, al momento della nascita dell’uni- verso (circa 13 miliardi di anni fa), un super- calcolatore in grado di esaminare mille miliar- di di percorsi al secondo, e avesse cominciato subito a fare eseguire l’algoritmo, sarebbero necessari ulteriori 8000 miliardi di anni per completare l’analisi. Il commesso viaggiatore non sarà certo molto soddisfatto del software acquistato, e si domanderà (correttamente) quali studi abbia compiuto il programmatore.
1 0
0 0 1
4. TRATTABILITÀ E INTRATTABILITÀ. LA CLASSEP
In termini più precisi, l’algoritmo precedente ha complessità asintotica Θ(N!), dove N è la di- mensione dei dati in ingresso. Un algoritmo di questo tipo è del tutto inutile, salvo che per ca- si semplicissimi. Gli algoritmi che utilizzano, al crescere delle dimensioni dell’input una quan- tità di risorse “irragionevolmente alta” sono chiamati intrattabili, altrimenti sono trattabili.
La definizione di (in)trattabilità dipende crucial- mente da cosa si intenda con la locuzione “una quantità di risorse irragionevolmente alta”. Ci limitiamo per ora allo studio del solo tempo di esecuzione, rimandando al paragrafo 8 per considerazioni sulle altre risorse.
Una funzione di complessità fattoriale o espo- nenziale porta a una rapida esplosione dei tem- pi di esecuzione in funzione delle dimensioni n dell’ingresso, come si vede nella tabella 1, in cui si ipotizza di eseguire gli algoritmi su un cal- colatore in grado di svolgere un milione di ope- razioni elementari al secondo.
Per esempio, se un algoritmo per il problema del commesso viaggiatore avesse complessità Θ(2n) potrebbe forse arrivare a trattare casi con una quarantina di città, ma certo non potrà mai risolvere problemi con 100 città o più. Gli algorit- mi di complessità Θ(n log(n)), come per esem- pio i migliori algoritmi di ordinamento visti nel terzo articolo di questa serie, possono in pratica risolvere problemi di dimensione qualunque, ma anche algoritmi in Θ(n2) o in Θ(n3) sono ra- gionevolmente efficienti in molte situazioni pra-
tiche. La distinzione fondamentale sembra quin- di fra gli algoritmi che hanno complessità espo- nenziale (o più alta) e quelli di complessità poli- nomiale. Un algoritmo ha complessità polino- miale se la sua complessità non cresce più rapi- damente di un polinomio, ossia se è Θ(nk) per qualche k. Per esempio, n log(n) ha complessità polinomiale (perché cresce più lentamente del polinomio n2, mentre 2ncresce più rapidamente di qualunque polinomio). Secondo gran parte della comunità scientifica, questa considerazio- ne è generale: gli algoritmi trattabili sono solo quelli di complessità polinomiale.
Questa definizione di trattabilità può tuttavia sconcertare. Infatti, mentre può essere chiaro che funzioni polinomiali dell’ordine di n3sono ragionevolmente efficienti, appare alquanto singolare mettere in questa classe polinomi del tipo n10300. Tuttavia, la scelta è basata su criteri empirici: non si conoscono problemi di reale importanza pratica con complessità polinomia- le così elevata, ma anzi per ogni problema inte- ressante o si è trovato un algoritmo ragionevo- le, ad esempio in Θ(n4), oppure si sa, o si pen- sa, che il problema abbia complessità più che polinomiale (tipicamente esponenziale). Se tuttavia un giorno si trovasse un problema im- portante per cui i migliori algoritmi funzionano in tempo n10300, la scelta “efficiente = polino- miale” andrebbe rivista.
A questo punto, il commesso viaggiatore del- l’esempio potrebbe pensare che basti assume- re un programmatore più bravo che, con un po’
di tempo e d’ingegno, realizzerà certo un algo-
Dimensione Tempo di esecuzione in secondi in funzione della dimensione del problema
n n log (n) n2 n3 2n n!
10 0,00003 0,0001 0,001 0,001 3,6288
20 0,00008 0,0004 0,008 1,05 2,4 · 1012
30 0,0001 0,0009 0,027 1073,742 2,6 · 1026
50 0,0003 0,0025 0,125 1,1 · 1 09 3 · 1058
100 0,0007 0,01 1 1,3 · 1024 9,3 · 10151
1000 0,001 1 1000 1,1 · 10295 ≈103000
106 19,93 106 1012 ≈10300000 ≈106000000
TABELLA 1
Tempi di esecuzione in secondi per algoritmi di varia complessità. Un “passo” elementare = un microsecondo
1 0
0 0 1
ritmo che sia stavolta polinomiale anche nel ca- so peggiore.
La TCC però ci insegna che ciò è assai improba- bile, pur non potendo escluderlo del tutto. Co- me è possibile?
La TCC si propone non tanto di trovare algorit- mi per risolvere i problemi, ma di dimostrare che per certi problemi non vi è nessun algorit- mo trattabile in tutti i casi. Si è visto, nel primo e nel secondo articolo di questa serie, che è possibile dimostrare che per certi problemi non esiste alcun algoritmo. Invece ora interes- sa sapere se esiste un algoritmo che sia anche efficiente. La TCC studia la complessità dei problemi, ossia la complessità del migliore al- goritmo possibile (noto o ignoto che sia) che risolve un certo problema.
In generale, i problemi per i quali esiste un al- goritmo trattabile sono anch’essi detti trattabi- li, altrimenti sono intrattabili. Quindi la classe dei problemi trattabili coincide con la classe dei problemi che ammettono l’esistenza di algorit- mi polinomiali per la loro soluzione (su una Macchina di Turing). Tale classe viene chiamata P (Polinomiale).
5. LA CLASSE NP E I PROBLEMI
NP-COMPLETI
Abbiamo già visto nella terza parte di questa serie come a volte sia possibile trovare un li- mite inferiore alla complessità di un proble- ma, ossia una soglia di efficienza algoritmica invalicabile: una volta trovato un algoritmo che appartenga alla classe di complessità asintotica di questa “soglia”, per quanti sforzi si facciano per ideare nuovi algoritmi, non si riesce a oltrepassare questa barriera, perché i nuovi algoritmi portano soltanto miglioramen- ti marginali (per esempio, abbassano le co- stanti moltiplicative, oppure migliorano le prestazioni per valori limitati delle dimensioni dei dati o in casi particolari).
Trovare limiti inferiori alla complessità di un problema è difficile: si deve prescindere da ogni particolare algoritmo risolutivo, ma la di-
mostrazione deve essere valida per tutti i possi- bili algoritmi (inclusi anche quelli non ancora inventati). La cosa sembra ancora più complica- ta in quanto apparentemente questo procedi- mento di dimostrazione deve essere ripetuto per ogni diverso problema. Poiché nella pratica vi sono migliaia e migliaia di problemi da risol- vere con il calcolatore sembra che il procedi- mento abbia poca speranza. Si è però scoperto che moltissimi problemi interessanti, in appa- renza assai diversi fra loro, sono in un certo senso “riducibili” a pochi problemi fondamen- tali. In particolare, esiste una grande varietà di problemi di notevole interesse pratico, detti problemi NP-completi, per cui esistono forti motivi per pensare che siano tutti intrattabili, cioè non appartengano alla classe P, senza però poterlo asserire con certezza.
Nessuno è mai riuscito a escogitare un algorit- mo polinomiale per calcolare una soluzione del problema del commesso viaggiatore. Tuttavia, è molto facile trovare un algoritmo polinomiale (addirittura in tempo lineare Θ(n)) per verificare se un percorso dato sia una soluzione: basta calcolare la lunghezza del percorso e confronta- re il risultato con K. Lo stesso algoritmo “stupi- do” che prova tutti i percorsi è strutturato in una parte che genera un percorso e in un’altra che lo verifica. Si è constatato che la facilità nel verifi- care una soluzione piuttosto che nel calcolarla è un fatto di validità generale, tanto da meritare addirittura l’introduzione di una classe di com- plessità ad hoc. La classe dei problemi per cui esiste un algoritmo polinomiale nelle dimensio- ni dell’input (per una Macchina di Turing) per controllare che una soluzione data sia corretta si chiama NP (Nondeterministico Polinomiale)1. Tutti i problemi della classe P sono ovviamente anche in NP. Esistono problemi in NP che non sono in P?
Uno degli sviluppi più sorprendenti e impor- tanti della teoria della complessità è stato scoprire che un gran numero di problemi prati- ci interessanti sono contenuti nella classe NP, definita inizialmente a partire da modelli ma- tematici puramente teorici, ma senza potere
1 NP non significa Non Polinomiale, come talvolta erroneamente si ritiene. Il termine “Nondeterministico” deriva invece da un particolare modello di macchina di Turing (TM), la TM nondeterministica, in grado di risolvere un problema “indovi- nandone” una soluzione finita e poi verificandola. Anche se i modelli nondetermistici non sono fisicamente realizzabili come tali, ogni funzione calcolabile da una TM nondeterministica può essere calcolata anche da una TM (ma, almeno ap- parentemente, in un tempo maggiore).
1 0
0 0 1
stabilire se essi si trovino anche in P. Quindi, per essi si può determinare efficientemente se una soluzione data è accettabile, ma non è no- to se sia possibile anche calcolare efficiente- mente una soluzione. Quasi tutti questi pro- blemi, come quello del commesso viaggiato- re, costituiscono una sottoclasse particolare di NP, quella dei problemi NP-completi (riqua- dro a piè pagina). I problemi NP-completi han- no un ruolo davvero speciale nella classe NP:
basterebbe trovare un algoritmo che risolva in tempo polinomiale un solo problema NP-com- pleto per consentire di risolvere in tempo poli- nomiale qualunque altro problema della clas- se NP (e pertanto in tal caso si sarebbe dimo- strato che P = NP).
Nonostante gli sforzi trentennali di moltissimi ricercatori, con tecniche matematiche e algorit- miche molto sofisticate, nessuno ha mai trova- to un algoritmo polinomiale per un problema NP-completo (ad esempio, il migliore algoritmo noto per il commesso viaggiatore funziona in tempo Θ (n22n)), ma nessuno ha mai nemme- no dimostrato che tale algoritmo non esiste. È tuttavia assai più facile, per un certo problema, scrivere un algoritmo e valutarne la comples- sità che provare che non esiste nessun algorit- mo di un certa complessità. Quindi la maggior parte dei ricercatori ritiene che effettivamente P sia diverso da NP: se così non fosse, qualcu- no probabilmente avrebbe ormai trovato un al- goritmo polinomiale per un problema NP-com-
pleto, mostrando così che tutti i problemi in NP sono anche in P.
6. COME AFFRONTARE IN PRATICA PROBLEMI NP-COMPLETI
Nella pratica, di solito i problemi NP-completi sono considerati intrattabili “per ignoranza”.
Quando infatti si trova che un problema inte- ressante è NP-completo, si può tranquillamen- te interrompere la ricerca di un algoritmo poli- nomiale, in quanto è assai improbabile riuscire a trovarlo, perché questo equivarrebbe a risol- vere così la questione P = NP che ha impegnato a lungo e senza successo menti fra le più bril- lanti dei nostri tempi.
Questo però non significa che, poiché un pro- blema intrattabile è assolutamente senza spe- ranza di risoluzione algoritmica efficiente in ge- nerale, allora possiamo evitare anche di prova- re a risolverlo. Si possono infatti applicare tec- niche algoritmiche ben note, che permettono di risolvere il problema in modo efficiente non in generale ma in casi particolari, o a costo di ac- cettare soluzioni anche un po’ imprecise.
Ad esempio, sono stati trovati algoritmi ben più efficienti di quello banale per risolvere il pro- blema del commesso viaggiatore. Nel maggio 2004, uno di questi algoritmi ottimizzati [6], im- plementato su un cluster di un centinaio di workstation, ha risolto il problema della visita ottima di tutte le 24,978 città della Svezia, im-
Riduzione e NP-completezza
La tecnica utilizzata per definire la classe dei problemi NP-completi va sotto il nome di riduzione polinomiale. L’idea di riduzione è già stata introdotta nei primi articoli di questa serie, e viene qua estesa alla riduzione polinomiale. Per semplicità, ci limitiamo a problemi di decisione, ossia a problemi p la cui risposta su un dato d sia p(d) = SI o p(d) = NO. Per esempio, il problema del commesso viaggiatore è un problema di decisione: dati il numero delle città, le loro distanze e la lunghezza massima K, esiste un percorso che passa per tutte le città una sola volta ed è di lunghezza inferiore a K? In generale, per risolvere un problema di de- cisione p sui dati d, al posto di definire direttamente un algoritmo per p si può utilizzare la nostra capacità di risolvere un altro problema di decisione p´, diverso da p. Ci basta trovare un algoritmo R che, preso il nostro problema p e i dati d, genera dati d´per il problema p´ in modo che la risposta a p´ sui dati d´ sia la stessa di quella di p per i dati originali d, ossia p(d) = p´(d´). Per esempio, se p(d) è SI, anche p´(d´) è SI, e viceversa. L’algoritmo R è detto algoritmo di riduzione. Se R ha complessità polino- miale si dice che p è riducibile polinomialmente a p´. Se la soluzione di p´ fosse in tempo polinomiale, allora avremmo trovato un algoritmo polinomiale anche per p: basta applicare la riduzione (tempo polinomiale) e poi risolvere il problema p´ (in tempo po- linomiale, su dati d´ la cui dimensione non può che essere polinomiale in d). La tecnica di riduzione è spesso applicata anche in pratica per costruire algoritmi, ma è fondamentale per mostrare che un problema è NP-completo. Formalmente, un problema p´
è NP- completo se ogni problema p della classe NP è riducibile polinomialmente a p´. Quindi, se fosse noto un algoritmo poli- nomiale per risolvere anche un solo un problema NP-completo, come quello del commesso viaggiatore, si saprebbe automati- camente risolvere in tempo polinomiale ogni altro problema della classe NP: le due classi di complessità coinciderebbero (P = NP). Se invece P ≠ NP, ci sarebbero problemi in NP, fra cui tutti i problemi NP-completi, non risolubili in tempo polinomiale. Per mostrare che un problema p in NP è NP-completo, occorrerebbe dimostrare che tutti i problemi in NP sono riducibili polinomial- mente ad esso, il che è ovviamente assai difficile. Tuttavia, una volta trovato il primo problema NP-completo (per esempio, il co- siddetto problema della soddisfacibilità di formule booleane, dimostrato NP-completo da S. Cook nel 1971), è poi sufficiente mo- strare che questo problema è riducibile polinomialmente a p.
1 0
0 0 1
piegando “solo” l’equivalente di 80 anni di cal- colo per un singolo calcolatore. La caratteristi- ca di questo algoritmo (e altri simili) è quello di avere ancora complessità esponenziale nel ca- so peggiore, ma di essere polinomiale in vari casi particolari, spesso di notevole rilevanza pratica. Tuttavia è sempre possibile costruire esempi, anche piccoli, in cui anche questi algo- ritmi ottimizzati non riescono a trovare la solu- zione ottima in tempi ragionevoli.
Esistono varie tecniche per risolvere numerosi (ma non tutti!) problemi intrattabili d’importan- za pratica. Per esempio, si possono “scegliere bene” quali alternative considerare per prime, per eliminare precocemente quelle che sicura- mente non sono accettabili per la soluzione.
Nel problema del commesso viaggiatore, ad esempio, al posto di calcolare la lunghezza di un intero percorso A B C D, possiamo calcolare dapprima la distanza da A a B: se questa supe- ra già il limite K, si può fare a meno di prendere in esame tutti i percorsi che cominciano con A B. Questo semplice accorgimento può ridurre notevolmente il numero di passi dell’algoritmo in molti casi pratici, anche se il caso peggiore resta sempre intrattabile.
Spesso gli algoritmi sono basati su strategie empiriche (dette “euristiche”) che cercano di arrivare velocemente a una soluzione corretta in molti casi particolari. Per esempio, si potreb- be costruire un percorso scegliendo ogni volta la città più vicina fra quelle non esplorate: se la città più vicina ad A fosse D, e poi la più vicina a D (fra B e C) fosse C, allora l’algoritmo potrebbe esaminare solo la lunghezza del percorso A D C B. Questa tecnica, che può anche essere com- binata con la strategia precedente, si comporta bene in vari casi speciali, ma in generale non può garantire di trovare un risultato corretto in modo efficiente.
Altre tecniche euristiche più sofisticate rinun- ciano a produrre una soluzione esatta, ma si ac- contentano di garantire un limite all’errore. Per esempio, un algoritmo approssimato potrebbe per esempio, scorrettamente rispondere “NO”
quando invece esiste un percorso di lunghezza inferiore a K, ma che non si scosta da K di più, ad esempio, del 5%. In questo modo, molti pro- blemi intrattabili, ma non tutti, diventano riso- lubili in modo efficiente.
Infine, esistono algoritmi esponenziali che in pratica si comportano sempre molto bene, in
quanto l’esponenzialità corrisponde a casi pa- tologici che di fatto non accadono mai. Un esempio in tal senso è il famoso algoritmo del simplesso, usato per la soluzione di problemi di programmazione lineare, che in pratica è sem- pre polinomiale anche se il caso peggiore è esponenziale. Si noti però che il problema della programmazione lineare è comunque nella classe P: i “casi patologici” esponenziali per- tanto non corrispondono a un problema intrat- tabile, ma solo a un particolare algoritmo che riesce a essere particolarmente efficiente in pratica proprio “rischiando” ogni tanto di non riuscire di fatto a terminare la computazione.
7. LA TESI ESTESA DICHURCH-TURING
Un dubbio naturale che potrebbe sorgere ri- guarda proprio le fondamenta della TCC: la complessità di un problema può dipendere dal modello di calcolo? Cosa succederebbe se al posto di una macchina di Turing si usasse un al- tro modello?
Per esempio, abbiamo definito P usando un modello di calcolo sequenziale (la macchina di Turing), che esegue cioè una sola operazione per volta. I modelli di calcolo paralleli, come un sistema multiprocessore, possono invece ese- guire molte operazioni contemporaneamente.
Per esempio, il problema del commesso viag- giatore potrebbe essere risolto molto fretta, per un qualunque numero N di città, a patto di ave- re un calcolatore con N! processori: ogni pro- cessore potrebbe essere dedicato al calcolo della lunghezza di un singolo percorso. Di fatto, però questo modello parallelo è impossibile da realizzare: per risolvere in questo modo il pro- blema per N = 100 occorrerebbero 10157proces- sori, ossia un numero probabilmente molto su- periore agli atomi nell’universo. La classe P può tuttavia essere definita in modo del tutto equi- valente utilizzando modelli paralleli, a patto di considerare come “tempo” il lavoro totale svol- to dai vari processori. La TCC ha verificato che ogni altro modello “ragionevole” studiato fino- ra definisce esattamente le stesse classi di complessità.
Le classi di complessità, pur essendo definite in base a modelli di calcolo, che apparentemente poco o nulla hanno a che vedere con i problemi concreti, consentono di classificare la grande
1 0
0 0 1
maggioranza delle migliaia e migliaia di proble- mi computazionali che sorgono nella pratica.
Questo “irragionevole successo” dei nostri mo- delli matematici, e la sostanziale indipendenza dei risultati della teoria dal modello computa- zionale scelto, ha portato, su basi empiriche, a ritenere che le classi di complessità come P cat- turino aspetti importanti del mondo reale. Da qui, la cosiddetta tesi estesa di Church-Turing:
La classe di complessità P cattura esattamente la nozione di algoritmo calcolabile in tempo polinomiale, qualunque sia il modello di calco- lo fisicamente realizzabile usato per definirla.
Poiché si ritiene che “efficiente” sia sinonimo di
“risolubile in tempo polinomiale”, la tesi implica che la classe P cattura tutti i problemi pratici la cui risoluzione può essere considerata “efficien- te”. La tesi è l’analogo per la complessità com- putazionale della tesi di Church-Turing, illustrata nel primo articolo di questa serie, che afferma che i problemi computabili sono esattamente quelli risolubili con le macchine di Turing.
Di recente, una sfida alla tesi estesa di Church- Turing è arrivata da un modello di computazio- ne fondato sulle proprietà della meccanica quantistica, che introduce una forma di paralle- lismo illimitato, basato sui cosiddetti bit quan- tistici (qubit). Al momento, i calcolatori quanti- stici realizzati secondo questo modello sono di dimensioni molto ridotte (per esempio, sette bit quantistici, equivalenti a 27= 128 bit tradi- zionali, quando invece le memorie dei calcola- tori sono misurate in miliardi di bit). È ancora argomento di accesa discussione fra i fisici se calcolatori quantistici di dimensioni utili siano fisicamente realizzabili oppure no. Cosa succe- derebbe se lo fossero? La tesi originale di Chur- ch-Turing è ancora verificata dai modelli quanti- stici: ciò che è calcolabile da un calcolatore quantistico è calcolabile anche da una macchi- na di Turing. Tuttavia, ci sono alcuni dubbi sulla validità della tesi nella sua forma estesa. Si è infatti trovato almeno un caso di problema inte- ressante in NP, per il quale non si conoscono al- goritmi polinomiali, ma che è invece risolubile in tempo polinomiale da un modello quantisti- co. Il problema è la scomposizione di un nume- ro in fattori primi, di grande importanza ad esempio nella crittografia. Shor [4] ha trovato un algoritmo polinomiale per risolvere il pro- blema con un modello quantistico. Quindi, se effettivamente il problema non fosse in P e se i
“calcolatori quantistici” fossero fisicamente realizzabili, la tesi estesa di Church-Turing non sarebbe valida. Tuttavia, sembra che l’impatto di una simile innovazione sulla TCC sarebbe li- mitato: non sono mai stati trovati altri problemi intrattabili interessanti per cui la computazione basata su bit quantistici potrebbe portare a so- luzioni sostanzialmente più efficienti. In parti- colare, ma nessuno l’ha dimostrato, si sospetta che i modelli basati sui bit quantistici non siano in grado di risolvere in tempo polinomiale i pro- blemi NP-completi, ma solo alcuni problemi in NP che si ritiene non siano in P. L’unico altro ca- so interessante trovato finora in cui i modelli quantistici migliorano notevolmente l’efficien- za rispetto a quelli tradizionali è nel caso della ricerca in un database non ordinato (che co- munque è già polinomiale).
Esistono infine numerosi modelli teorici in cui si possono risolvere in tempo polinomiale proble- mi intrattabili, e altri che possono addirittura ri- solvere problemi indecidibili per le Macchine di Turing. Tuttavia, l’esistenza di un modello teori- co “Super-Turing” non implica che questo sia anche fisicamente realizzabile, e le attuali pro- poste sembrano assai lontane dalla realtà fisi- ca (ad esempio, alcuni modelli effettuano cal- coli con precisione infinita, o usano improbabili operazioni quantistiche non lineari).
8. COMPLESSITÀ SPAZIALE E CIRCUITALE
Ci siamo concentrati finora sui limiti legati al tempo di esecuzione degli algoritmi. Simili con- siderazioni valgono anche considerando lo spazio di memoria o più in generale la dimen- sione dei circuiti che devono essere costruiti per calcolare un certo algoritmo, come illustra- to dal seguente esempio, dovuto a Stockmeyer, di problema intrattabile.
Consideriamo il problema della progettazione di protocolli di comunicazione. I protocolli possono essere inizialmente definiti da un’opportuna for- mula, utilizzando una notazione (linguaggio) tratta dalla logica matematica. La formula descri- ve quali sono le sequenze di scambio accettabili fra i partecipanti al protocollo. In base alla formu- la, si può progettare un circuito digitale che rea- lizza il protocollo dato. Un circuito digitale è defi- nito combinando opportune porte logiche. Una porta logica è un elemento che svolge un’opera-
1 0
0 0 1
zione booleana elementare, come per esempio la complementazione di un segnale da “vero” a
“falso” o da “falso” a “vero”. Le porte logiche so- no gli elementi costitutivi di qualunque calcola- tore e la loro definizione astratta è indipendente dalla tecnologia con cui sono effettivamente rea- lizzate (attualmente, quella elettronica), che in- fluenza solo il costo, l’ingombro, i consumi e la velocità del circuito, ma non il valore calcolato. È chiaro che, prima di progettare e realizzare fisica- mente un circuito che implementa una certa for- mula, conviene convincersi che la formula stessa sia corretta. Utilizzando uno dei possibili linguag- gi logici adatti alla definizione di circuiti digitali, è stato dimostrato che un circuito in grado di verifi- care la correttezza (più precisamente, la validità) di una formula con al più 616 simboli (che quindi occupa meno di una diecina di righe di questa pagina, dimensione in realtà assai ragionevole per descrivere un protocollo) richiede perlomeno 10123porte logiche: “se anche le porte avessero la dimensione di un protone e fossero connesse da fili infinitamente sottili, il circuito riempirebbe densamente l’intero universo conosciuto” [5].
9. CONCLUSIONI
Lo studio delle limitazioni su quello che può es- sere realizzato è molto importante in ogni cam- po dell’ingegneria. Per esempio, la termodina- mica è di fondamentale importanza nella co- struzione di macchine, poiché stabilisce che non possiamo creare energia dal nulla, che non possiamo realizzare il moto perpetuo e, più in generale, che vi sono limiti invalicabili all’effi- cienza di una qualunque macchina termica. Al- lo stesso modo, la teoria della computabilità insegna che alcuni problemi non hanno solu- zione algoritmica su una macchina calcolatrice, mentre la teoria della complessità stabilisce che altri problemi non hanno alcuna una solu- zione algoritmica efficiente.
Questo studio teorico, e soprattutto la questio- ne se P = NP, ha notevoli conseguenze pratiche.
Per esempio, quasi tutti i metodi di crittografia a chiave pubblica, usati universalmente per la si-
curezza delle transazioni sul World Wide Web, sono basati sull’ipotesi che non esistano algorit- mi efficienti per scomporre un numero grande nei suoi fattori primi. Poiché il problema della scomposizione in fattori primi è nella classe NP (per quanto non si sappia se NP-completo), allo- ra se fosse P = NP (per esempio, se esistesse un algoritmo efficiente per risolvere il problema del commesso viaggiatore) esisterebbe anche un algoritmo efficiente per questa scomposizione, e si potrebbero carpire facilmente numeri di car- te di credito, conversazioni confidenziali e se- greti militari. Come già osservato, per questo problema esiste in realtà un algoritmo efficiente usando modelli di calcolo quantistici, la cui rea- lizzabilità fisica non è tuttavia stata ancora pie- namente dimostrata.
Bibliografia
La “bibbia” della NP-completezza, è stata a lungo il vo- lume di Garey e Johnson, ora forse un po’ datato. Più recente e generale il testo di Papadimitriou, mentre in italiano si veda Mandrioli e Ghezzi. Il riferimento al sito [6] contiene un esempio di soluzione del problema del commesso viaggiatore. Il libro di Harel [7], infine, è un testo divulgativo sulle limitazioni dei computer, sia per le questioni di indecidibilità che di intrattabilità.
[1] Mandrioli D., Ghezzi C.: Fondamenti di Informa- tica Teorica. UTET, Milano.
[2] Garey M. R., Johnson D. S.: Computers and In- tractability. W. H. Freeman, San Francisco, 1988 (prima edizione: 1979).
[3] Papadimitriou C.: Computational complexity.
Addison Wesley Longman, 1994.
[4] Shor P. W.: Polynomial-Time Algorithms for Pri- me Factorization and Discrete Logarithms on a Quantum Computer. In Proc. 35thAnnual Sym- posium on the Foundations of Computer Scien- ce, IEEE Computer Society Press, Los Alamitos, California, 1994, p. 124.
[5] Stockmeyer L.: Classifying the computational complexity of problems. J. Symbolic logic, Vol. 52, 1987, p. 1-43.
[6] http://www.tsp.gatech.edu/sweden/index.html [7] Harel D.: Computers, Ltd. Oxford University
Press, 2000.
PIERLUIGISANPIETROè professore straordinario di Ingegneria Informatica presso il Politecnico di Milano ed è do- cente del corso di Ingegneria del Software. I suoi interessi di ricerca sono rivolti ai metodi e agli strumenti per la specifica e la verifica di sistemi informatici ad alta criticità, e alla teoria degli automi e dei linguaggi formali.
