Un problema del millennio

La prova del nove

La nostra (lontana?) esperienza di studenti delle scuole medie ed elementari ha certamente incluso l'incontro con la famosa prova: il controllo, cioè, della correttezza della soluzione di un'operazione o di una equazione o comunque di un problema di Matematica. Semplici procedure, come la ben nota prova del nove, hanno verosimilmente allietato qualche nostro pomeriggio di giovani scolari. Converremo tutti che questo esercizio di verifica può essere talora noioso, arido e poco stimolante. Pur tuttavia, ha proprietà di sicurezza e meccanicità che non possono non essere apprezzate, almeno da uno studente alle prime armi, ancora inesperto di tutte le sottigliezze matematiche: pochi passaggi, automatici e ripetitivi, bastano per confermare che la risposta precedentemente acquisita è esatta oppure, malauguratamente, a contestarla e a costringerci a ricominciare. In effetti, risolvere un esercizio è pur sempre una scommessa, una sfida piena di incognite, di incertezze e di pericoli. Verificarne la soluzione – una volta che è stata acquisita – può essere talora un'antipatica appendice, ma ha il pregio di una placida procedura lontana da ogni rischio.
Anche per problemi più seri ed attuali, cercare una soluzione può essere esperienza delicata e impegnativa, mentre controllare la soluzione trovata richiede talvolta una semplice occhiata. Ad esempio, pensiamo alla decomposizione degli interi positivi N nei loro fattori primi. Recuperare i fattori primi di un assegnato numero composto N è, ancor oggi (almeno per N grande), esercizio complicato e difficile, privo di procedure adeguatamente veloci e soddisfacenti; invece, verificare la decomposizione di N, una volta che se ne conoscono i fattori, è impegno di poca spesa che si riduce ad una semplice moltiplicazione, gestibile in pochi attimi con un comune calcolatore, anche quando N ed i suoi fattori sono numeri di molte cifre. Fortunati sistemi di crittografia a chiave pubblica (come il famoso RSA) basano la loro sicurezza ed efficienza sul dislivello ancora esistente tra determinare e verificare la decomposizione di un intero N.

Nasce allora la curiosità generale di confrontare da un lato le risorse necessarie per risolvere un problema, dall'altro quelle richieste per controllarne le soluzione. In particolare, ci possiamo domandare: se la verifica può essere svolta in modo rapido (come nel caso della decomposizione), può dirsi lo stesso della soluzione? L'esempio degli interi ci mostra che la questione ha aspetti intriganti e fascinosi, ma in qualche caso attende ancora una risposta definitiva. L'articolo che segue vuole discutere in maggior dettaglio l'intera questione e sottolinearne sorprendenti venature, sottintesi e difficoltà.

P e NP

Come detto, il nostro intento è confrontare i tempi di soluzione e di verifica di un problema o, più esattamente, dei migliori algoritmi che gli si applicano. Naturalmente, un'analisi precisa e rigorosa della questione richiederebbe che prima si convenissero chiare definizioni teoriche di che cosa si intende per problema e per algoritmo e di come se ne misura l'efficienza temporale.

Alan Turing

Noi qui ci accontentiamo di prendere atto che queste esigenze hanno adeguata risposta (si veda, ad esempio, [1] o [2]): un preciso formalismo matematico descrive che cosa è un problema e la classica tesi di Alan Turing degli anni Trenta del secolo scorso sembra suggerire ancora un buon modello teorico di quel che si deve intendere per algoritmo (o, meglio, per problema dotato di algoritmo). Quanto alla misurazione dell'efficienza di una procedura (di soluzione o di verifica), c'è una proposta in Informatica teorica, che è variamente attribuita (ad Edmonds, Cook, Karp) e risale ai tardi anni Sessanta. Sostiene che un algoritmo A è efficiente quando lavora in tempo al più polinomiale rispetto alla lunghezza dell' input: in dettaglio, ci deve essere un polinomio pA(x) – che ha coefficienti interi, assume valori positivi da un certo punto in poi e dipende solo da A – tale che la computazione di A su input di lunghezza al più n (a cui è possibile rispondere) si svolge entro pA(n) passi (almeno per n sufficientemente grande). Si propone così una stima asintotica del tempo di lavoro dell'algoritmo, tesa a valutarlo come funzione di n e a studiarne il comportamento per n che tende all'infinito: idea ragionevole, visto che quel che ci interessa per dichiarare A efficiente non è tanto il suo modo di trattare certi specifici particolarissimi input ma un quadro complessivo delle sue capacità di lavoro, al variare di tutti gli input e delle loro lunghezze. Da questo punto di vista, la tesi di Edmonds, Cook e Karp si può riassumere (in termini un po' rozzi e brutali) nello slogan “efficiente=polinomiale”.
Naturalmente, si tratta di proposta discutibile (e discussa). In effetti, se è facile ammettere che un algoritmo A sia efficiente quando lavora in tempo lineare oppure anche quadratico rispetto alla lunghezza dell' input (in altre parole, quando il corrispondente polinomio pA è di primo oppure di secondo grado), quando il grado del polinomio cresce e si vanno a scomodare situazioni quali , si può realmente dubitare che A lavori davvero in modo rapido. D'altra parte, sembra difficile individuare un miglior livello di separazione e cioè un grado d tale che gli algoritmi che lavorano in tempo asintotico limitato da x^d siano ritenuti veloci mentre quelli che impiegano x^d+1 passi non lo siano più. Perché accettare d ed escludere d +1? Almeno a livello teorico, non ci sono argomentazioni sufficienti per motivare una simile opzione. Così, la tesi di Edmonds-Cook-Karp è comunemente accettata, sia pure con le riserve sopra accennate. Semmai, ne sottolineiamo un aspetto che ci pare indiscutibile: siccome la funzione esponenziale x→2^x supera asintoticamente i polinomi di ogni possibile grado, un algoritmo che impiega tempo 2ⁿ oppure superiore rispetto alla lunghezza n dei suoi input è da ritenersi lento e impraticabile (né ci pare che il senso comune possa qui smentire l'affermazione teorica).
Così, rassicurati dal rigore scientifico circa la definizione di problema, algoritmo ed efficienza, possiamo far libero riferimento ad un'idea intuitiva di questi tre concetti e procedere nel nostro scopo. Anzi definiamo, per fissare le idee, P come la classe dei problemi che ammettono un algoritmo efficiente di soluzione (P sta per polinomiale, ovviamente) e NP come la classe dei problemi che ammettono un algoritmo efficiente di verifica delle soluzioni.
È chiaro che P⊆NP. La nostra curiosità è se vale addirittura l'uguaglianza P=NP, se dunque un problema che ha procedura rapida di verifica ammette anche un algoritmo (magari più lento ma ancora efficiente, cioè polinomiale) per trovare le soluzioni. Questo è quanto vorremmo discutere qui. Ciò stabilito, vale comunque la pena di fermarsi un attimo e spendere qualche parola sui motivi per cui dovremmo appassionarci (o almeno qualcuno dovrebbe appassionarsi) a questa domanda.

Clay Mathematics Institute

Che si tratti di questione rilevante, si deduce facilmente vedendola inserita tra i sette Problemi del Millennio , quelli che il Clay Mathematics Institute di Cambridge, Massachussetts, ha segnalato come i più significativi e difficili nella ricerca matematica del 2000. Maggiori informazioni sull'argomento, e la lista completa dei sette problemi, possono trovarsi in [3] oppure direttamente nel sito del Clay Institute, www.claymath.org/millennium. Visitandolo, il lettore potrà osservare come un premio di un milione di dollari è promesso a chi risolverà una qualunque delle sette questioni, il che costituisce già da sé ottimo motivo per interessarsi anche di P=NP. C'è poi chi può essere attirato dalla questione a prescindere dal denaro, solo per la sua valenza teorica. Ma ciò che può accrescere la curiosità generale è lo spettro quasi illimitato delle sue applicazioni particolari, la quasi infinità dei problemi per i quali non è difficile intravedere un algoritmo di verifica efficiente, ma appare tragicamente complicato individuare una procedura rapida di soluzione.

Pensiamo, ad esempio, alla questione di riconoscere i numeri primi e a quella di decomporre i numeri naturali composti N, cui già abbiamo accennato nell'introduzione. Come già osservato, quando conosciamo i fattori primi di N, non è difficile né lento controllare la decomposizione (e cioè se N è davvero il risultato che si ottiene moltiplicandoli): anche se N ha 1000 cifre in base 10 ed i suoi singoli fattori sono “quasi altrettanto” lunghi, i moderni calcolatori impiegano tempi relativamente brevi per la verifica. Tuttavia, allo stato attuale delle conoscenze, non sono noti algoritmi capaci di decomporre N in tempo rapido (cioè al più polinomiale rispetto alla lunghezza di N, secondo i parametri sopra stabiliti). Il problema di riconoscere se N è primo (in genere chiamato problema di primalità) è lievemente diverso ed apparentemente più semplice. Non ci interessa infatti, per N composto, conoscere i suoi fattori ma soltanto dichiararlo tale. La relativa verifica è ovviamente rapida, almeno quando N è composto; controllare se N è primo (quando è primo) può invece riservare qualche maggior ostacolo, visto che non si tratta più di confermare una decomposizione che conosciamo ma di escludere ogni possibile fattorizzazione non banale di N. Esistono comunque algoritmi rapidi (di una qualche maggiore complicazione teorica) che sanno compiere rapidamente questa verifica. Del resto, nel 2002, tre ricercatori indiani (Agrawal, Kayal e Saxena) hanno finalmente proposto un procedimento capace di scoprire rapidamente se un fissato N è primo oppure no: l'algoritmo funziona infatti al più in tempo x¹¹ rispetto alla lunghezza dell' input e recenti perfezionamenti di Lenstra e Pomerance hanno abbassato a x⁶ questa soglia (si veda [6]).
Tra le questioni che appartengono a NP, ce ne sono alcune che hanno un interesse particolare per un motivo che adesso cerchiamo di spiegare. Ammettiamo di trovare un problema che dichiaratamente sta in NP ma di cui riusciamo a provare per qualche via teorica che non può stare in P. Deduciamo ovviamente, e correttamente, che P≠NP. Ma supponiamo adesso di considerare un altro problema S in NP e di riuscire a dimostrare che S∈P. Commetteremmo un grosso errore matematico e logico a dedurre P=NP. Un esempio non può costituire una dimostrazione. Tuttavia, capita talora (anche nella vita di tutti i giorni) che esistano persone o riferimenti o valori così generali da rappresentare adeguatamente classi ampie ed articolate, coagulandone perfettamente le sensazioni e le aspettative. Come nel patto dei 3 (o 4) moschettieri di Dumas, vale il principio uno per tutti (e tutti per uno): il singolo rappresenta la totalità e la totalità si riconosce nel singolo. Lo stesso avviene nel caso di P e NP. Esistono davvero problemi S di NP capaci di rappresentare tutti gli altri loro confratelli, nel senso che – per dirla in modo rozzo e vagamente impreciso – se S appartiene a P, allora P=NP, ovvero, per usare termini più rigorosi e corretti, qualunque problema S' in NP si può tradurre in modo rapido in S, e quindi, se S ammette un algoritmo veloce di soluzione, anche S' lo eredita. Questi problemi S' si dicono NP-completi. Dunque, S è NP-completo se valgono due condizioni:

• S ∈ NP;
• per ogni problema S' ∈ NP , esiste un procedimento effettivo che traduce in tempo polinomiale ogni istanza di S' in una istanza di S (quest'ultima condizione si sintetizza dicendo che S è NP-arduo ).

Dunque, per provare che P=NP, basta dimostrare che uno tra i possibili problemi NP-completi ammette un algoritmo rapido di soluzione: si applica cioè il principio dei moschettieri ( uno per tutti ).
Il primo problema che fu provato NP-completo (da Cook, nel 1971) riguarda una questione di Logica elementare, che ha il nome di Problema della Soddisfacibilità della Logica Preposizionale ma che è anche conosciuto con la sigla (più immediata) SAT. Lo discuteremo nel prossimo paragrafo in modo che ci auguriamo accessibile anche ai non addetti ai lavori. Ma, come vedremo sempre nello stesso paragrafo, SAT è solo il capostipite di una dovizia di esempi NP-completi.
La situazione, che si viene così a configurare per ognuno di questi problemi S, è curiosa ed intrigante. Infatti, per ciascuno di essi, è facile verificare una soluzione (se la si conosce) ma è difficile trovarla, anzi è così impegnativo come risolvere l'intera questione P=NP. Non sorprenderà che una tale disparità di situazione sia ottima fonte di ispirazione per certe esigenze della moderna crittografia. La nostra epoca, infatti, va utilizzando sempre più intensamente le potenzialità dei calcolatori per eseguire pagamenti, certificazioni, firme, sottoscrizioni “virtuali”, cioè telematiche. Operazioni così delicate richiedono ovviamente strumenti capaci di garantire la privacy degli utenti e metterla al riparo da eventuali malintenzionati. In particolare, nasce l'esigenza di criptare i messaggi e i documenti trasmessi in rete in modo che la decodifica sia facile per l'interlocutore desiderato, ma complicata e difficile ai pirati di Internet. Le caratteristiche dei problemi NP-completi sembrano corrispondere perfettamente a questa situazione. L'analogia può dunque ispirare adeguati sistemi crittografici. Illustreremo nel sesto paragrafo un esempio di queste applicazioni, che del resto verranno ulteriormente discusse alla fine del lavoro.
Completiamo questa sezione dicendo che il problema della primalità ovviamente non è NP-completo, a meno che P=NP; sta infatti in P. Quanto alla fattorizzazione, la questione è aperta ma criptosistemi largamente diffusi come il famoso RSA (si veda ad esempio in [7]) si basano sulle difficoltà che ancora la riguardano e ne distinguono tempi minimi di soluzione e verifica.

Un problema di Logica elementare

Aristotele particolare - Raffaello Scuola di Atene

Il problema di cui si parla nel titolo è quello della Soddisfacibilità della Logica Proposizionale. A dispetto del nome vagamente altisonante, si tratta di questione relativamente semplice. Lo introduciamo come un gioco enigmistico, secondo l'approccio di [8]. Si tratta di considerare il nostro usuale alfabeto a, b, c ,…, o anche una sua estensione potenzialmente infinita, e di formarvi parole (dunque sequenze ordinate finite di lettere) nel rispetto delle seguenti regole:

• ogni parola può accogliere lettere sia maiuscole che minuscole, A, a, B, b e così via (dunque SteLla , oppure sTELLa ,o StelA sono almeno inizialmente ammesse);
• non sono comunque consentite ripetizioni della stessa lettera nella stessa parola (il che esclude, tra gli esempi appena proposti, sTELLa , che contiene L due volte);
  
• neppure la presenza di una lettera sia maiuscola che minuscola nella stessa parola è permessa (e dunque anche SteLla va rifiutata).

Chiamiamo normali le parole che si ottengono in questo modo: così StelA , LEtra , mATeiC , PriSTeM sono parole normali. Il gioco consiste allora in quanto segue: dato un qualunque insieme finito di parole normali, vogliamo sapere se esiste una parola normale che interseca tutte quelle dell'insieme, nel senso che condivide con ciascuna di esse almeno un simbolo.
A scanso di equivoci, sottolineiamo che il problema non richiede espressamente di trovare una soluzione ma semplicemente di valutare se una soluzione è possibile oppure no. Adesso mescoliamo un po' le carte e vediamo come il nostro gioco di maiuscole e minuscole vada a nascondere qualcosa di teoricamente più rilevante. Interpretiamo ogni lettera minuscola come una affermazione, ad esempio:

a come “questo articolo mi piace”, s come “domani piove” e la corrispondente maiuscola come la negazione di quella affermazione, dunque:
A come “questo articolo non mi piace” , S come “domani non piove”.

Immaginiamo poi che ogni parola normale vada a rappresentare la disgiunzione delle proposizioni (affermate o negate) associate alle sue lettere: così sA significa “domani piove” oppure “questo articolo non mi piace” (che può anche intendersi “se questo articolo mi piace, domani piove” ). Infine, interpretiamo un insieme finito di parole normali con la congiunzione delle disgiunzioni che le singole parole nascondono. Così, se t traduce l'affermazione “prendo l'ombrello”, l'insieme di sA e t rappresenta: “se questo articolo mi piace, domani piove” e “prendo l'ombrello”.
Non è difficile convincersi che, in questa ottica, il semplice esercizio di trovare una parola normale che condivide almeno un simbolo con ogni parola data va a nascondere qualcosa di apparentemente più impegnativo e cioè individuare un'opinione coerente che vada a trovare in ciascuna delle parole coinvolte almeno una proposizione (affermata o negata) con cui concorda. Il problema che ne risulta è, allora, quella questione classica di Logica elementare cui accennavamo all'inizio del paragrafo.
Che cosa ha di così nascosto e misterioso questo problema (e dunque, per dirla in modo meno ufficiale e impegnativo, la ricerca di parole normali capaci di intersecare un certo insieme dato)? Non è difficile convincersi che la nostra questione appartiene a NP : se conosciamo una soluzione adeguata ad un certo insieme, verificarla – controllare cioè che condivida almeno un simbolo con ciascuna delle parole dell'insieme– non è esercizio troppo lungo da svolgere. Non è invece evidente che il problema appartenga a P, ammetta cioè anche un algoritmo rapido di ricerca delle soluzioni. Ad esempio, se l'insieme di partenza ha parole che coinvolgono complessivamente n lettere (minuscole o maiuscole), le possibili soluzioni e dunque le parole che possono formarsi, anche a meno di permutazioni, con queste n lettere, sono 2ⁿ visto che ogni lettera può comparire (almeno a priori) maiuscola oppure minuscola. Dunque, il numero dei controlli richiesti da un esame pignolo di tutti i possibili candidati, al fine di valutare che almeno uno di essi funzioni, richiede 2ⁿ controlli: troppi, visto che n è indice della lunghezza dell'insieme input.

Kurt Gödel

Questo non esclude, in linea di principio, che altri procedimenti più profondi e brillanti possano ottenere esiti più veloci. Ma, nel 1971, Cook dimostrò un risultato fondamentale e, per certi versi, sorprendente, e cioè che trovare un algoritmo rapido (=polinomiale) per SAT equivale a risolvere positivamente il problema P=NP.

In dettaglio: per ogni problema S in NP, esiste un procedimento effettivo che traduce in tempo polinomiale ogni input relativo ad S in una istanza di SAT in modo tale che l'input originario appartiene a S se e solo se la corrispondente istanza di SAT ha soluzione positiva. Conseguentemente, se SAT ammette un algoritmo rapido di soluzione, lo stesso vale per ogni S in NP (tramite la precedente riduzione a SAT). L'idea della dimostrazione di Cook è semplice e brillante, tende infatti a codificare ed esprimere gli input del generico problema S tramite condizioni su lettere maiuscole e minuscole che formino istanze di SAT. Naturalmente, la sua realizzazione richiede l'uso di ingegnose tecniche combinatorie.
Dunque SAT, per quanto elementare possa sembrare il suo enunciato, accoglie in sé tutta la complessità della questione P=NP : è NP -completo, come preannunciato nel paragrafo precedente. Più precisamente, SAT è il primo caso storicamente provato di problema NP-completo. Tuttavia, non è l'unico. Anzi, SAT è il capostipite di una lunga progenie di esempi. Già nel 1972, dunque un anno dopo il Teorema di Cook, Karp propose una lista di 21 problemi NP-completi S. La strategia per riconoscerli tali è, tutto sommato, meccanica e ripetitiva. Si tratta di mostrare che SAT (oppure qualche altro esempio chiave già riconosciuto come NP-completo) si può ricondurre con una procedura polinomiale a S: tramite SAT, o comunque tramite l'altro esempio di riferimento, tutto NP si riduce di conseguenza in tempo polinomiale a S.
Si prova in questo modo che anche 3SAT – la versione di SAT che coinvolge soltanto parole normali che si compongono di esattamente 3 lettere– condivide la NP-completezza di SAT.
Dunque, il problema che si ricava riformulando la questione introdotta all'inizio del paragrafo con parole di sole 3 lettere include l'intera complessità di P=NP. In effetti, l'intero SAT può essere codificato con opportuni argomenti combinatori nel contesto di parole con 3 lettere. Lo stesso vale ovviamente quando le lettere coinvolte in ogni parola sono più di 3. Come detto, 3SAT compariva già nella lista di Karp del 1972.
Invece, 2SAT –la variante con parole di 2 lettere– appartiene a P. Vediamo perché. Abbiamo un insieme finito arbitrario di parole normali con 2 lettere (maiuscole o minuscole) e vogliamo sapere se c'è una parola normale che le interseca tutte. Anzi, cerchiamo un algoritmo che sappia risponderci in tempo rapido (in relazione alla grandezza dell'insieme finito a cui viene applicato) e non dipenda, ovviamente, dall'insieme particolare per cui lo si usa. Consideriamo la prima lettera in gioco: a, senza perdita di generalità. Possiamo crederla (ed accettare a nella possibile soluzione) oppure rifiutarla (ed accogliere allora A ). Scegliamo a, tanto per fissare le idee. A questo punto, tutte le parole che contengono a sono intersecate. Quelle che invece includono A (diciamo, Ab o AD ) non possono più condividere A; così la possibile soluzione deve accogliere b e D. Ma a questo punto il ragionamento appena condotto si può ripetere per b e D: si va a creare, per questa via, una specie di effetto domino al termine del quale si va in tempi brevi ad individuare, oppure escludere, l'esistenza di una soluzione.
La passione per i problemi NP -completi non si è certo arrestata con la lista di Karp. Negli anni successivi (e fino ad oggi), da un lato si sono approfonditi vari aspetti teorici della NP-completezza, senza riuscire tuttavia a risolvere la questione P=NP, cioè a trovare un algoritmo rapido per un problema NP-completo; dall'altro, si sono scoperti sempre nuovi esempi, tutti con un ovvio fondamento combinatorio, ma distribuiti in svariate aree della ricerca scientifica: in Matematica, in Informatica, in Biologia, in Chimica, in Enigmistica ed ancora in altri settori. Libri classici, come [5] trattano in dettaglio la NP-completezza e ne illustrano gli esempi chiave. La lista dei problemi NP -completi è costantemente aggiornata nel Journal of Algorithms, a cura di D. Johnson, ed anche da svariati siti Internet. Citiamo per tutti:

http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html,

il quale propone e discute un centinaio di problemi. Noi ci limiteremo, nelle pagine che verranno, ad illustrarne alcuni che ci sembrano simpatici e rappresentativi.

Guerre stellari

Nelle nostre famiglie terrestri è già talora difficile andare d'accordo in due, marito e moglie. Figuriamoci allora quanti e quali contrasti, e forse guerre, potrebbero sorgere in qualche mondo lontano, nel quale i sessi ufficiali fossero 3 o più di 3 e dunque i matrimoni si combinassero in 3 o più di 3.
In effetti, la situazione è considerata e descritta con tocco crepuscolare e delicato nel libro Neanche gli Dei (The Gods Themselves) del maestro della fantascienza Isaac Asimov.

Isaac Asimov

A menti più superficiali e terrene (?!?) verrà comunque da pensare che anche le agenzie matrimoniali dovrebbero risentire di qualche maggiore difficoltà, di tipo sia combinatorio che caratteriale. In effetti, il Problema del Matrimonio nei comuni 2 sessi può formularsi come segue. Sono dati:

• due insiemi finiti U e D di ugual cardinalità q (l'insieme degli uomini e quello delle donne );
• una relazione S nel prodotto cartesiano U×D di tutte le possibili coppie (uomo, donna): la relazione di reciproca attrazione o simpatia .

Si tratta allora di combinare q matrimoni in modo da accontentare tutti gli uomini e le donne coinvolte e dunque determinare, se possibile, un sottoinsieme M di S (quello dei matrimoni, appunto), ancora di cardinalità q, in modo che ogni uomo ed ogni donna compaiano in una (ed una sola) coppia di M. A chi lavora nelle agenzie matrimoniali della nostra Terra, sarà consolante sapere che il Problema del Matrimonio a 2 Sessi, usualmente denotato 2DM (Two-dimensional matching), ha un procedimento veloce di soluzione: gli aspiranti sposi non dovranno aspettare troppo per coronare le loro aspirazioni (se mai è possibile coronarle). Ma, quando i sessi diventano 3, ad esempio nel mondo di Asimov, le cose si complicano. Infatti il Problema del Matrimonio a 3 Sessi (3DM, Three-dimensional matching) deve affrontare:

• tre insiemi finiti A, B, C di ugual cardinalità q (corrispondente ai tre sessi possibili);
• una relazione S nel prodotto cartesiano A×B×C di tutte le possibili terne (a, b, c): la relazione di reciproca attrazione o simpatia tra i 3 personaggi coinvolti.

Bisogna allora combinare q matrimoni in modo da accontentare tutti gli interessati e dunque determinare, se possibile, un sottoinsieme M di S (quello dei matrimoni, appunto), ancora di cardinalità q , in modo che ogni elemento di A, di B e di C compaia in una (ed una sola) terna di M. Ebbene, nessun algoritmo veloce di soluzione è conosciuto per 3DM (e per i problemi dei matrimoni in dimensioni superiori a 3). Anzi, se questo algoritmo ci fosse, potremmo dedurne P=NP nel senso illustrato nel precedente paragrafo: il Problema del Matrimonio a 3 Sessi è NP -completo (e dunque è forse bene che i sessi siano soltanto 2…).
Il riferimento ai numeri 2 e 3 non è una coincidenza casuale. Il lettore avrà già constatato, infatti, che la situazione che si va presentando per 2DM e 3DM corrisponde perfettamente a quella che distingue 2SAT da 3SAT. In effetti, ci sono opportune procedure che collegano in tempo polinomiale le istanze di nDM (per n=2, 3) a quelle per nSAT. Per tal via, 2DM preserva le prerogative di efficienza che ha 2SAT mentre 3DM si trova a condividere i limiti ed i dubbi degli algoritmi conosciuti per 3SAT. Del resto, 3DM compariva già nella lista di Karp del 1972.

Il commesso viaggiatore ed altre storie di grafi

Un concetto matematico facile da introdursi (ma non da studiarsi) e comunque utile nella formalizzazione di tanti problemi di carattere combinatorio, anche in Informatica e in altri settori scientifici diversi dalla Matematica, è quello di grafo. Nella versione più semplice, un grafo è un insieme G con una relazione binaria A (di adiacenza) simmetrica ed irriflessiva. Da un punto di vista intuitivo, possiamo immaginare gli elementi (o, come anche si dice, i vertici) a, b, … di G come possibili tappe di un itinerario stradale ed ogni coppia (a, b) ∈ A come una via diretta che collega a e b: strada a doppio senso, perché A è simmetrica, e con estremi tra loro diversi a≠b perché A è irriflessiva.
La nozione di grafo pare dunque molto facile ed accessibile. Si tratta comunque di impressione superficiale e menzognera. Infatti, proprio in ragione della loro semplicità, i grafi possono codificare qualunque struttura algebrica, anche apparentemente più complicata, quale potrebbe essere un gruppo, o un campo, ed addirittura accogliere per questa via l'intera complessità della Matematica. Non è allora stupefacente che, tra i problemi NP-completi, molti facciano riferimento proprio al concetto di grafo. Ci limitiamo qui a citarne quattro, fra quelli che compaiono nella lista di Karp, nell'ordine:

(a) Il Problema del Ricoprimento dei Vertici;

(b) il Problema del Clique;

(c) il Problema dell'Insieme Indipendente;

(d) il Problema del Commesso Viaggiatore (o del Circuito Hamiltoniano).

Vediamoli in dettaglio:

a), b), c) I dati di partenza dei tre problemi sono esattamente gli stessi: un grafo finito (G, A) ed un intero positivo k (minore o uguale del numero n dei vertici di G). In tutti e tre i casi, ci chiediamo se esiste un sottoinsieme G´ di G di cardinalità al più k . Il criterio di ricerca di G´ varia però a seconda del problema:

(a) chiede che G´ sia quel che si dice un ricoprimento dei vertici di G e cioè che ogni percorso (a, b) in A ammetta almeno un estremo a o b in G´;

( b ) invece domanda che ogni coppia di vertici distinti di G´ sia congiunta da un percorso in A (G´ si dice allora un clique);

(c) infine richiede che G´ sia indipendente, in altre parole che nessuna coppia di vertici di G´ sia congiunta da percorsi di A.

Non è difficile accorgersi che i tre problemi sono tra loro collegati. Infatti, un sottoinsieme G´ di G è un ricoprimento dei vertici se e solo il suo complementare G–G´ è indipendente. Ambedue le condizioni, poi, equivalgono a chiedere che G–G´ sia un clique non in (G, A) ma nel grafo che se ne ottiene unendo proprio quelle coppie di vertici distinti che A lascia separati. In ciascuno dei tre casi, è facile convincersi che una eventuale soluzione G´, se conosciuta, può essere rapidamente controllata. Ma, quanto a decidere l'esistenza di G´, le cose si complicano: in linea di principio, i sottoinsiemi di G da coinvolgere nella ricerca sono tanti quanti il coefficiente binomiale

In effetti, i tre problemi sono –come detto– NP-completi. Ciascuno dei tre codifica in tempo polinomiale 3SAT (e trasmette ovviamente agli altri due questa proprietà).

(d) Il Problema del Commesso Viaggiatore si riferisce invece ad una questione più pratica, quella che può riguardare, appunto, un commesso viaggiatore che ogni mattina organizza l'itinerario giornaliero che lo porti da tutti i clienti previsti e poi lo riconduca a casa nel minor tempo possibile, evitando dunque di passare due volte dallo stesso punto e dalla stessa strada. In termini rigoro si, possiamo immaginare di avere un grafo G (in cui informalmente i vertici rappresentano l'abitazione del commesso viaggiatore e gli n distinti recapiti dei suoi clienti e i cui percorsi sono le strade che collegano tutte queste possibili tappe) e ci chiediamo se è possibile elencare gli elementi di G: g(0), g(1), …, g(n) in modo tale che (g(i), g(i +1))∈ A per ogni i < n e finalmente (g(n), g (0))∈A (in altre parole, assumendo che g(0) denoti la casa del commesso e g(i) quella del cliente i -mo per ogni i=1, …, n, devono esserci strade dirette che congiungono g(i) a g(i +1) per i<n e poi l'ultimo indirizzo g(n) a g (0), evitando così all'affaticato commesso di dover percorrere più volte parte del suo itinerario). Dispiace dover comunicare al nostro commesso viaggiatore, e a chiunque fosse interessato a situazioni analoghe, che la questione (ufficialmente denominata del Circuito Hamiltoniano ) è NP-completa perché ad essa si può ridurre in tempo polinomiale il Problema del Ricoprimento dei Vertici, sopra considerato.

Zaini, francobolli
e codici segreti

Il Problema dello Zaino è la questione che in genere ci affligge la notte prima della partenza per le vacanze: abbiamo uno zaino di volume V e vogliamo infilarci gli oggetti 0, 1, …, n-1, rispettivamente di volume v(0), …, v(n -1). Ognuno di essi ci pare, infatti, indispensabile per il buon esito delle nostre ferie. Ci chiediamo se è possibile sceglierne alcuni in modo da colmare esattamente lo zaino e dunque se esista un sottoinsieme I di {0, …, n -1} tale che

(intendiamo che V, v(0), …, v(n -1) ed ovviamente n siano interi positivi ed assumiamo poi che lo zaino non sia rigido e si presti ad essere deformato in ogni modo possibile, così che la soluzione dipenda solo dal volume degli oggetti coinvolti e non dalla loro figura).
L'esperienza comune ci insegna che la questione è tutto meno che semplice: in genere, la sera prima delle ferie, i tentativi si sprecano e le ore volano prima che gli oggetti siano finalmente sistemati, se mai lo sono, in modo soddisfacente. Spesso è il sonno, o la stanchezza, a dettare (o forse rinviare) la soluzione. Del resto, la difficoltà ha un suo logico fondamento visto che le possibili combinazioni di oggetti da infilare nello zaino sono tante quanti i sottoinsiemi di {0, 1, …, n -1 } , e cioè 2ⁿ.
Una versione più rassicurante e tranquilla del problema si riferisce ad una lettera da affrancare per un valore totale V e ad n francobolli 0, …, n -1 rispettivamente di costo v (0), …, v(n -1) tra i quali scegliere in modo tale da raggiungere esattamente il valore V. Stavolta la ricerca può apparire meno traumatica. Pur tuttavia, da un punto di vista matematico, la questione è esattamente la stessa e può prevedere un numero esponenziale di tentativi prima di ottenere, se possibile, la giusta soluzione.

Non v'è dubbio che il problema, comunque lo si voglia presentare, stia in NP : se conosciamo l'opportuno insieme I, verificare che (in relazione agli input V, n, v(0), …, v(n -1)) è controllo rapido di poca fatica. Ma il Problema dello Zaino (Knapsack secondo la terminologia ufficiale) è anche NP-completo: trovare una procedura efficiente di soluzione equivale a risolvere l'intera questione P=NP (e chi ci riuscisse potrebbe passare in vacanza tutto il resto della sua vita). In effetti, il Problema dello Zaino compare già (almeno implicitamente) nella lista di Karp; una tecnica per provarne la NP-completezza consiste nel riferirsi a 3DM e nel codificarlo in tempo polinomiale appunto in Knapsack. Il Problema dello Zaino ha, tra l'altro, dirette applicazioni alla moderna Crittografia. Le illustriamo brevemente, anche per riprendere ed approfondire con questo esempio il discorso già iniziato nel secondo paragrafo sui collegamenti tra P = NP e la Crittografia.

Osserviamo anzitutto che il Problema dello Zaino può avere talora rapida soluzione, ammesso che la sequenza v(0), …, v(n -1) sia opportunamente costruita. Ammettiamo, ad esempio, che v(0), …, v(n -1) sia supercrescente, cioè tale che, per ogni i<n, v(i) sia maggiore della somma dei volumi degli oggetti che lo precedono, . Così 2, 3, 7, 15, 31 è supercrescente perché 2<3, 2+3<7, 2+3+7<15 e 2+3+7+15<31 mentre la sequenza (crescente) 2, 5, 4 non lo è perché 2+4 non è minore di 5. È facile trovare algoritmi rapidi di soluzione per il Problema dello Zaino per sequenze supercrescenti. Infatti, supponiamo che v(0), …, v(n-1) formino una tale sequenza (e fissiamo anche V). Consideriamo, per cominciare, v(n-1). Se v(n-1)>V, dobbiamo evidentemente escluderlo dallo zaino ma, se v(n-1) è invece minore o uguale a V, dobbiamo obbligatoriamente inserirlo e coinvolgerlo nella eventuale soluzione: v(n-1) non può essere infatti sostituito dalla somma dei volumi restanti, che gli è minore per ipotesi, e dunque non riesce a raggiungere il valore V e riempire in tal modo lo zaino.
Dunque, se c'è soluzione, v(n-1) vi partecipa. A questo punto, consideriamo v(n -2) e confrontiamolo con il volume complessivo restante (ancora V se v(n-1) è stato escluso, V–v(n-1) altrimenti), ripetendo la procedura. Applicando questo metodo, recuperiamo alla fine una soluzione del problema, se esiste.
Anzi, si può osservare che la soluzione, se c'è, è anche unica. Ad esempio, consideriamo V=24 e la sequenza supercrescente di sopra 2<3<7<15<31. Siccome 31>24>15, si comincia con l'escludere v(4)=31 e coinvolgere v(3)=15. A questo punto, si calcola il volume residuo 24-15=9 e si nota che v(2)=7<9, ammettendo di conseguenza v(2) nell'eventuale soluzione. Da 9-7=2< 3, si deduce finalmente che v(1) va escluso e v(0) va coinvolto. Si conclude che il problema ha, in questo caso, soluzione 2, 7, 15.
In conclusione, il Problema Supercrescente dello Zaino ha un algoritmo rapido di soluzione mentre non si conosce nessuna procedura veloce per il Problema generale dello Zaino (ed anzi si paventa che non ci sia). La situazione si presta ad applicazioni crittografiche. Per introdurle, fissiamo anzitutto il nostro contesto. Abbiamo due interlocutori A e B che vogliono comunicare tra loro in modo sicuro, senza che i loro messaggi siano intercettati e soprattutto capiti da un qualche malintenzionato C. Conseguentemente A cerca di cifrare le sue comunicazioni a B in modo che B possa rapidamente decodificarle, ma C non sappia infrangerle in alcun modo. Possiamo anche immaginare che il messaggio di A a B si componga di sequenze di lunghezza n di bit 0 o 1.

A questo proposito, notiamo che il Problema dello Zaino si può riformulare come segue: fissati V, n, v(0), …, v(n-1), possiamo cercare, anziché un sottoinsieme I di {0, …, n -1} tale che una sequenza ( e0, …, en-1) di bit 0 o 1 per cui (basta intendere che I è formato proprio dagli indici i<n per cui ei=1). Risolvere il problema per un dato input V, n, v(0),…, v(n -1) significa decidere l'esistenza di una tale sequenza ( e0, …, en-1).

Ritorniamo allora ai messaggi di B e A . Una possibile strategia, che A può seguire per organizzare il suo criptosistema, consiste nello scegliere anzitutto una sequenza supercrescente v(0),…, v(n-1). Ci sono semplici metodi per generarla. Ad esempio, A può prendere n +1 interi positivi arbitrari z(0),…, z(n -1), z(n) e calcolarsi: v(0)=z(0), v(1)=v(0)+z(1), per ogni i<n

(che formano ovviamente una sequenza supercrescente), anzi computare anche:

Ad esempio, gli interi positivi 2, 1, 2, 3, 4, 2 generano in questo modo la sequenza supercrescente 2, 3, 7, 15, 31 di cui sopra (ed inoltre m = 60). A questo punto, A maschera la sequenza prodotta v(0), …, v(n-1) moltiplicandone gli elementi modulo m per un qualche intero a primo con m e dunque invertibile modulo m. Nell'esempio, si può scegliere a=7 (infatti 7 è primo con 60 ed il suo inverso modulo 60 è 43) ed ottenere da 2, 3, 7, 15, 31 la nuova sequenza 14, 21, 49, 45, 37 (modulo 60) che non è più supercrescente, perché la moltiplicazione per 7 ha rimescolato (modulo 60) l'ordine degli elementi coinvolti: ad esempio 31 · 7 = 217 è congruo a 37 modulo 60. In generale, scelto a, A computa anzitutto l'inverso a' di a modulo m (operazione facile e veloce, grazie a metodi elementari di Teoria dei numeri) e poi soprattutto la sequenza w(0), …, w(n-1) definita ponendo, per ogni i<n, 0<w(i)<m e w(i) congruo ad a·v(i) modulo m (cioè v(i) congruo ad a ´· v (i) modulo m ). Ovviamente, la nuova sequenza w(0), …, w(n -1) può non essere supercrescente ed anzi A avrà comunque cura che non lo sia.
A questo punto, A comunica a B (ed anzi divulga a tutti gli interessati) w (0), …, w(n-1) (la chiave pubblica di codifica da utilizzare per scrivergli) e mantiene gelosamente segreti m, a e v(0), …, v(n-1) (che costituiscono la sua chiave privata di decriptazione).
La codifica, l'invio e la decodifica di un eventuale messaggio avvengono come segue. Come detto, l'interlocutore B lo scrive sotto forma di sequenze (e0, …, en-1) di lunghezza n di bit scelti tra 0 e 1. Per ogni sequenza, B calcola e lo trasmette ad A. Con le informazioni segrete in suo possesso, A può recuperare (e0, …, en-1) nel modo che adesso descriviamo. Dapprima, A moltiplica il messaggio cifrato ricevuto W per l'inverso a' di a modulo m e poi calcola il resto V´ di questo prodotto nella divisione per m; poi osserva:

Siccome tanto V che V´ sono interi positivi minori di m , A deduce V´=V. Allora A , ricavato , decodifica facilmente (e0, …, en-1) perché la sequenza v(0), …, v(n -1) è supercrescente.

Invece un pirata C, che pure riesca ad intercettare W ed intenda recuperare (e0, …, en-1), conoscendo soltanto la sequenza (non supercrescente) w (0), …, w(n -1), si trova di fronte ad una istanza del Problema generale dello Zaino con tutte le difficoltà che ne derivano.
In conclusione, Knapsack (ed altri problemi NP-completi) possono suggerire sistemi crittografici per lo scambio sicuro di messaggi. Quello appena descritto è un semplice esempio (ideato da Merkle ed Hellman alla fine degli anni Settanta).
Ad onor del vero, dobbiamo confessare che si tratta di un criptosistema troppo semplice, non affidabile né sicuro. In effetti, già nel 1982, pochi anni dopo la sua pubblicazione, ci fu chi osservò come le sequenze pubbliche w (0), …, w(n-1), pur non essendo supercrescenti come quelle private, hanno comunque una natura particolare (si ottengono da sequenze supercrescenti moltiplicando per un fattore costante modulo un intero m pure costante) ed ammettono conseguentemente un loro specifico algoritmo rapido di soluzione che, pur senza avere la pretesa di soddisfare il Problema generale dello Zaino, riesce comunque ad infrangerne con successo questo caso particolare. Va anche detto che, a seguito di questa osservazione, si studiarono perfezionamenti del criptosistema di Merkle ed Hellman capaci di restaurarne l'affidabilità.

L'orario delle lezioni

Il Problema dell'Orario è una di quelle antipatiche incombenze cui occorre far fronte all'inizio di ogni anno accademico o scolastico. Un disgraziato docente viene delegato a risolverlo e si trova così di fronte alla difficoltà di preparare un orario delle lezioni che concili le esigenze dei colleghi, quelle degli studenti e quelle ovvie di rispetto dei regolamenti didattici. L'impegno è ostico e quasi mai il risultato riesce ad accontentare tutti gli interessati, a prescindere dalla buona volontà e dalla capacità di chi si trova a svolgere la sfortunata incombenza. Del resto, che il problema non sia affatto semplice è anche testimoniato dal fatto che (allo stesso modo degli esempi elencati nei precedenti paragrafi) è NP-completo: non si conosce, in particolare, un algoritmo rapido che riesca a risolverlo in modo soddisfacente. Vediamo perché. Ovviamente, per apprezzare meglio il risultato di NP completezza, dobbiamo impostare in modo più preciso e matematico i termini della questione. Supponiamo allora che il Dipartimento (o l'Istituto) coinvolto ammettano n docenti e m classi di studenti ( n e m sono parte dell' input della questione). Sono inoltre fissati:

• l'insieme finito O delle ore settimanali in cui è prevista l'attività didattica;
  
• per ogni i=1, …, n, l'insieme P(i) delle ore in cui il professore i-mo è disponibile ad insegnare (così P(i) ⊆ O;
  
• per ogni j =1, …, m, l'insieme C(j) delle ore in cui la classe j-ma è disponibile ad ascoltare la lezione (dunque anche C(j) è sottoinsieme di O);
  
• per ogni i e j come sopra, il numero L(i, j) delle ore che il docente i è tenuto a svolgere alla classe j.

Tutti questi dati formano l'input del nostro problema. Ci chiediamo se sia possibile combinare un orario adeguato a queste premesse. In termini rigorosi, possiamo formalizzare questo obiettivo tramite una funzione:

f : {1, …, n}×{1, …, m} × O →{ 0, 1 }

(dove, per i=1, …, n , j=1, …, m ed o in O, f (i, j, o)=1 significa informalmente che l'insegnante i insegna alla classe j nell'ora o, e f (i, j, o)=0 l'esatto contrario) cui poniamo le seguenti richieste:

(a) per ogni scelta di i, j, o , se f(i, j, o)=1, allora o deve stare in P(i) e in C(j) (cioè deve appartenere all'insieme delle ore dichiarate disponibili dal professore i e dalla classe j);

(b) per ogni i e j, la somma dei valori f(i, j, o) al variare di o deve eguagliare L(i, j) (in altre parole, il numero complessivo delle ore di lezione che il professore i svolge alla classe j deve essere quello previsto dai regolamenti);

(c) per ogni j ed o, la somma dei valori f (i, j, o) al variare di i deve essere al massimo 1 (cioè non deve accadere che la stessa classe abbia alla stessa ora due docenti diversi);

(d) per ogni i ed o, la somma dei valori f (i, j, o) al variare di j deve essere al massimo 1 (cioè non deve accadere che lo stesso professore debba fare lezione alla stessa ora in due classi diverse).

Il Problema dell'Orario , usualmente denotato TT (dalle iniziali delle parole inglesi Time Table), chiede se esiste una tale funzione. È facile verificare che TT appartiene a NP: un algoritmo che ne verifica l'eventuale soluzione f si limita a controllarne le proprietà a), b), c) e d) e può svolgere in tempo rapido le relative computazioni. D'altra parte, esaminare tutte le possibili f richiede, almeno a priori, tempo esponenziale in n , m e nella cardinalità |O| di O, perché 2^n·m·|O| è il numero delle funzioni coinvolte. Naturalmente, questo non esclude a priori che esistano algoritmi rapidi di soluzione.
Nel 1976, Even, Itai e Shamir provarono, nuovamente utilizzando un'ingegnosa riduzione a 3SAT, che TT è NP-completo: dunque, escogitare una procedura generale capace di determinare rapidamente in quali casi si può compilare un buon orario, soddisfacente per tutti gli interessati, è difficile come risolvere P=NP. Chi ci riuscisse risolverebbe la questione chiave dell'Informatica teorica e potrebbe così esimersi dal preparare orari per tutto il resto della propria vita. Dettagli della dimostrazione si trovano in [4].

Enigmistica

Gli appassionati di enigmistica saranno contenti di sapere che anche il gioco del sudoku, così di moda negli ultimi tempi, è NP-completo: dunque non dovranno vergognarsi troppo quando la soluzione tarda ad arrivare.

Sono stati due ricercatori giapponesi, Yato e Seta, a dimostrare questa sorprendente proprietà nell'articolo [9]. Ecco qualche maggior dettaglio a questo proposito. Come tutti sanno, il problema del Sudoku si può formalizzare nei termini che seguono:

• sono dati un intero positivo n e una griglia di n²×n² caselle, suddivisa in n² quadrati di lato n, ciascuno composto da n×n caselle;
  
• alcune delle caselle sono riempite da un numero intero tra 1 e n²;
  
• si devono riempire le caselle bianche in modo tale che ogni riga, ogni colonna e ogni quadrato di lato n contenga esattamente tutti gli interi da 1 a n².

Ebbene, Yato e Seta hanno mostrato come tradurre SAT, e cioè il capostipite dei problemi NP-completi, nei termini di questo gioco combinatorio; ne hanno dedotto che anche il sudoku viene a ereditare da SAT la proprietà di NP-completezza.
Del resto, molte altre questioni di enigmistica condividono col Sudoku questa imbarazzante proprietà.

La Matematica
non guasta mai

Ci sono poi problemi NP-completi legati alla Matematica. In realtà, tutte le questioni elencate nei precedenti paragrafi riguardano sostanzialmente la Matematica, se non altro perché in linguaggio matematico possono essere formalizzate. Ma, in genere, quando si parla di Matematica (almeno nella accezione popolare del termine), si intendono numeri ed equazioni. Consideriamo allora un classicissimo sistema di equazioni, magari a coefficienti interi, e chiediamoci se ammette o no soluzioni. Ovviamente, dobbiamo preliminarmente specificare dove cerchiamo queste radici, se nello stesso anello Z degli interi o tra i razionali, i reali o addirittura i complessi. La risposta naturalmente può variare a seconda dell'ambiente in cui la cerchiamo.
Ciò premesso, lasciamo al sistema la più ampia libertà circa il numero delle equazioni e delle incognite o il grado dei polinomi coinvolti. Dunque, il problema ammette come input un sistema arbitrario di equazioni a coefficienti interi e tende a stabilire se esistono o no soluzioni reali, o complesse, o anche soltanto intere.

È facile notare che la questione che ne risulta è almeno NP ardua (a prescindere dal contesto in cui cerchiamo le radici). Infatti, il Problema dello Zaino vi può essere comunque codificato in modo rapido come segue. Consideriamo gli input (interi) V, v(0), …, v(n-1) di un'istanza di Knapsack. Vogliamo scegliere alcuni tra v(0), …, v(n-1) in modo tale che la loro somma sia proprio V; in altre parole, cerchiamo valori x0, …, xn-1 tra 0 e 1 per i quali valga l'equazione a coefficienti interi:

v(0)·x0+ … +v(n- 1)·xn -1= V

(per i < n , l'opzione xi=1 corrisponde ad includere v(i) tra gli oggetti selezionati per formare V; l'alternativa xi=0 significa escluderlo). La restrizione di xi ai valori 0,1 si traduce, per ogni i<n , nell'altra equazione xi·(xi–1)=0. Così, l'esistenza di una soluzione per il Problema dello Zaino si traduce nell'esistenza di una soluzione (intera, e dunque anche reale e complessa) al sistema formato in questo modo.
Siccome Knapsack è NP-completo, la questione che ne risulta è almeno NP-ardua, come già detto. Non è però chiaro se sia anche NP-completa, cioè se stia in NP. Il motivo del dubbio è chiaro. Consideriamo, infatti, il caso dei reali. Dobbiamo verificare l'esistenza di soluzioni reali del sistema. La prima idea che viene in mente è ovviamente quella di prendere una possibile soluzione e, appunto, controllare che funzioni. Ma c'è un guaio: i valori coinvolti sono, appunto, reali ed è oggettivamente difficile proporre un numero reale (con la sua infinita rappresentazione decimale) ad un computer. Il contesto continuo dei reali lega male con l'ambiente discreto che i calcolatori usualmente trattano. In verità, un computer non sa neppure controllare se un reale è uguale o no a zero. Ne scorre infatti le cifre intere o decimali ma, quand'anche giunga a leggerne migliaia, o milioni, ed a verificare che sono tutte uguali a 0, non può prevedere se le successive continuino ad annullarsi, oppure no. Il controllo dell'esistenza di soluzioni ha, quindi, inaspettate complicazioni e deve percorrere altre strade. Allo stato attuale delle conoscenze, si può solo dire che il problema dell'esistenza di soluzioni reali per sistemi a coefficienti interi è nella classe che in Teoria della Complessità si denota PSPACE e corrisponde ai problemi che si risolvono in spazio al più polinomiale, che cioè un calcolatore è capace di risolvere utilizzando un numero di locazioni di memoria limitato polinomialmente rispetto alla lunghezza dell' input. Della classe PSPACE, è noto che include NP ma non si sa se propriamente.
Se poi ci interessano soluzioni complesse, la questione ha risvolti ancora più intriganti. Il relativo problema (esistenza di soluzioni complesse per sistemi a coefficienti interi) è, ovviamente, NP-arduo ma, di nuovo, non si sa se sta in NP. È, invece, certamente collocato nella classe dei problemi AM, quelli che hanno procedure rapide capaci, se non di risolvere, almeno di convincere con piccola probabilità di errore dell'esistenza di soluzioni. A e M stanno qui a rappresentare le iniziali di Artù e di Merlino. Si immagina, infatti, che Merlino, da bravo mago, sappia tutto e che la sua autorità sia sufficiente (senza bisogno di troppe spiegazioni) a persuadere il giovane e fiducioso Artù. La classe AM è un'altra estensione (non si sa se propria) di NP , a sua volta inclusa in PSPACE .

Se dunque la classica esigenza di risolvere equazioni non corrisponde a problemi dichiaratamente NP-completi (almeno allo stato attuale delle conoscenze), c'è comunque ampio spazio per esempi di NP-completezza tra questioni che emergono in modo naturale nell'ambito matematico. Ne proponiamo alcuni.

(a) (Equazioni quadratiche diofantine) Consideriamo il caso particolare di un'unica equazione ax²+by+c=0 con a, b, c interi positivi; cerchiamo soluzioni x, y ancora intere positive. Il nome del problema fa riferimento al grado 2 dell'equazione e al matematico alessandrino Diofanto. In generale, la questione generale di individuare radici intere per sistemi a coefficienti interi (che ha appassionato molti, a cominciare da Diofanto nell'antichità) è tutto meno che banale: l'abbiamo evitata nelle considerazioni precedenti, ma le dedicheremo il prossimo paragrafo. Nel nostro caso particolare, se conosciamo x e y, è facile controllare che funzionano; ma stabilirne l'esistenza è un altro discorso e sconfina, appunto, nella NP-completezza.

(b) (Congruenze quadratiche) Consideriamo ancora, come nel caso precedente, tre interi positivi a, b e c. Ci chiediamo stavolta se è possibile trovare un intero positivo x < c tale che a sia il quadrato di x modulo b , cioè valga la congruenza x² ≡ a (mod b). Come si vede, siamo nel regno dell'Aritmetica e dell'Algebra classica. Ma la questione è, nuovamente, NP-completa.

(c) (Incongruenze simultanee) Stavolta abbiamo n coppie ordinate di naturali (a(i), b(i)) per i=1, …, n (anche n è un intero positivo arbitrario). Fissiamo a(i)<b(i) per ogni indice i; pensiamo dunque ad a(i) come ad un possibile resto della divisione per b(i). Un classico teorema di Aritmetica (il Teorema del Resto Cinese ) stabilisce condizioni sotto le quali possiamo trovare una comune soluzione intera x alle congruenze x ≡ a(i) (mod b(i)) per i=1, …, n. Afferma, in particolare, che x può trovarsi se b (1), …, b (n) sono a 2 a 2 primi tra loro. Ma a noi interessa qui, in un qualche senso, la situazione opposta, cioè se esiste un intero positivo x che non soddisfi nessuna delle precedenti congruenze x ≡ a(i) (mod b(i)). Potrà interessare sapere che il problema è NP-completo: facile da verificare, non si sa quanto rapido (o lento) da risolvere.

 

 

Un'attesa troppo lunga ed un'antipatica impossibilità

 

Se i problemi NP-completi condividono la fatalità di essere facili da controllare ma (almeno momentaneamente) lunghi da risolvere, ci sono questioni (matematiche e non) che trovano sorte anche peggiore. Ad esempio, ci sono problemi che certamente non hanno algoritmi rapidi né di soluzione né di verifica. Certe questioni algebrico-logiche sui reali e sui complessi (che estendono e complicano quella sulle radici reali, o complesse, dei sistemi di equazioni a coefficienti interi) richiedono tempo almeno esponenziale sia di soluzione che di verifica delle soluzioni. Una risposta può richiedere un'attesa proibitivamente lunga.

Ma c'è di peggio. Torniamo infatti al nostro sistema a coefficienti interi e chiediamoci se ammette o no soluzioni intere. Il problema è famoso. Interessò Hilbert, che lo pose al decimo posto nella lista di questioni rilevanti da lui proposte al Congresso internazionale di Parigi del 1900. Ebbene, un teorema di Matijasevic (cui contribuirono anche Davis, Putnam, Julia Robinson e altri) provò nel 1970 che la questione non ha algoritmo possibile (almeno se ci rifacciamo alla tesi di Turing e alla relativa definizione del concetto di algoritmo, cui abbiamo accennato nel secondo paragrafo). Non basta più avere la pazienza di aspettare un tempo esponenzialmente lungo o anche più esteso. L'attesa può essere infinita, perché la risposta non arriverà mai.

 

Che cosa ci riserva il futuro

 

Dopo aver proposto tanti curiosi esempi NP-completi, ci pare giusto accennare almeno un attimo alla possibile soluzione del problema P=NP. Come già insinuato nei paragrafi precedenti, la questione pare enormemente complicata e lontana dal chiarimento. I manuali di Informatica teorica e di Complessità (come [1] o [2], ad esempio) mostrano in abbondanza quale minuziosa analisi si è sviluppata per affrontarla e risponderle, quante e quali ulteriori classi di complessità (come PSPACE o AM ) sono state considerate per approssimare NP e possibilmente comprenderne la natura. Va poi aggiunto che certi sviluppi della Fisica, in particolare la nascita e la crescita di metodi e tecniche di Informazione quantistica, possono comunque alterare sostanzialmente il quadro del problema. Dal 1985 sono stati infatti introdotti a livello teorico i calcolatori quantistici, potenzialmente capaci di sviluppare in parallelo una quantità anche esponenziale di computazioni contemporanee e dunque di estendere la potenza del calcolo e di accelerarne le conclusioni. Ad esempio, esiste un recente (1994) ma già famoso procedimento quantistico di Peter Shor che, in teoria, sa decomporre in tempo rapido un numero composto N nei suoi fattori primi. È evidente che simili progressi possono diminuire sostanzialmente i tempi di computazione e dunque indurre a rivedere in modo sostanziale la questione P=NP ed anche le sue applicazioni a Crittografia ed informazione. Tuttavia l'ovvia premessa a tutti questi sviluppi è la possibilità pratica di costruire e far funzionare i calcolatori quantistici. Una loro realizzazione effettiva pare ancora ostacolata da serie difficoltà, sostanzialmente legate all'influsso che l'ambiente esterno può avere sul calcolatore e alla possibilità che ne alteri le computazioni. L'avvento effettivo dei metodi quantistici può quindi cambiare radicalmente il quadro di P e NP ma non sembra ancora prossimo ad attuarsi.

 

Bibliografia

 

 

[1] D. P. Bovet e P. Crescenzi, Teoria della Complessità Computazionale , Franco Angeli, 1991.

[2] F. Corradini, S. Leonesi, S. Mancini, C. Toffalori , Teoria della Computabilità e della Complessità , McGraw-Hill, 2005.

 

[3] K. Devlin , I Problemi del Millennio, Longanesi, 2004.

 

[4] S. Even, A. Itai, A. Shamir, “ On the Complexity of Timetable and Multicommodity Flow Problems” , SiamJ. Comp. 5, 1976, pp.691-698.

 

[5] M. Garey, D. Johnson , Computer and Intractability: A Guide to the Theory of Completeness, Freeman, 1979.

 

[6] A. Granville, “It is Easy to determine wheter a given Integer is Prime”, Bulletin American Mathematical Society , 42 (2005), pp. 3-38.

 

[7] S. Leonesi, S. L'Innocente, M. Marconi, C. Toffalori, “Primi e Segreti”, Lettera Matematica Pristem, 52, 2004 .

 

[8] D. Mundici , “ Algoritmi e Calcolabilità, Tesi di Church, Applicazioni della Logica all'Informatica”, L'Insegnamento della Logica , MPI-AILA, pp. 265-309.

 

[9] T. Yato, T. Seta, “Complexity and completeness of finding another solution and its application to puzzles”,IPSJ SIG Notes 2002-AL-87-2, IPSJ, 2002..