Esistono in natura i problemi computazionalmente difficili? E se esistono, come vengono risolti? Di questo, ma anche di alberi e passeri, e di tramonti, ce ne parla Manlio Gaudioso.

Premessa. Qualche mese fa, l’Università della Calabria ha conferito la Laurea Honoris Causa al Professor Georg Gottlob, del Dipartimento di Computer Science dell’Universitá di Oxford. In chiusura della sua lezione magistrale sulla complessità computazionale, il Professor Gottlob si è chiesto, un po’ scherzosamente e un po’ sul serio, se in natura esistano davvero problemi computazionalmente difficili, quelli che che gli esperti di complessitá chiamano “NP Completi”. Qui di seguito vi racconto di un problema difficile, appunto NP completo, che, in tutta apparenza, ogni sera la natura risolve su ogni albero.

Al tramonto. Immaginate un tardo pomeriggio d’estate in campagna, e voi che leggete un libro davanti a un gradevole panorama. La lettura è coinvolgente, assorbe la vostra attenzione e vi rende insensibili al frastuono che arriva dal grande tiglio vicino. Lo producono centinaia di passeri che svolazzano freneticamente tra rami e foglie, sbucando di tanto in tanto dalla chioma dell’albero, per poi rituffarvisi poco lontano. Sospendendo per un attimo la lettura, vi verrà di pensare, che so, al tripudio della natura, alla gioia e alla vitalità degli uccellini o all’armonia del creato.

Riflessioni sensate, che vi mettono in sintonia con l’ambiente intorno a voi. Ma certamente parziali. In effetti intorno al tiglio si sta combattendo, come tutte le sere, un’aspra battaglia di tutti contro tutti, per conquistare le posizioni migliori sull’albero, in vista della notte. Riprendete tranquillamente la lettura, ma intanto il buio è sceso e, alla fine, decidete di rientrare. Però a questo punto vi accorgete che, come d’incanto, l’albero è ora avvolto da un silenzio assoluto. Non si muove foglia e dei passeri non c’è più traccia, neanche visibile.

Proviamo ad interpretare l’accaduto. Forse i passeri sono stanchi di lottare oppure ciascuno ha ottenuto la posizione che preferiva, o, ancora, nessuno di loro ha interesse, o è in condizione, di mettere in discussione la posizione raggiunta. Potremmo quindi dire che un qualche equilibrio è stato conseguito. Verrebbe quasi voglia di cercare di descriverlo, questo equilibrio, ma da dove partire?

Certamente sono in campo due tipi di “soggetti”: da una parte i passeri, dall’altra le posizioni: una specie di domanda e di offerta che si confrontano. Il vero confronto, peró, é tra i passeri. É ragionevole pensare che tra loro, come in quasi tutti i contesti sociali, ci siano i forti, che sono in grado di imporre la loro volontá ai piú deboli. D’altro canto, i passeri sono individui e non é detto che esprimano tutti le medesime preferenze per le varie posizioni disponibili. Aggiungiamo anche che é difficile immaginare che un passero, appollaiato su un ramo, tra le foglie, abbia una visione completa di quello che accade sull’intero albero. Queste osservazioni ci suggeriscono una possibile formalizzazione matematica dell’equilibrio che, al calar della sera, viene raggiunto.

Il problema. Definiamo l’insieme dei passeri, \(I=\{1,\ldots,n\}\) e quello delle posizioni, \(K=\{1,\ldots,m\}\). Supponiamo anche che sia \(m >n\), che cioé ci siano piú posizioni disponibili che passeri.

Siano noti i seguenti dati:

• \(q_{ik}\), l’utilitá individuale, cioé una misura del gradimento, del passero \(i\) per la posizione \(k\), per \(i \in I\) e \(k\in K\);
• \(\mathcal{R}\subset I \times I\), una relazione di dominanza, con \((i,j) \in \mathcal{R}\) se il passero \(i\) domina quello \(j\), cioé é piú forte di lui ed é quindi in condizione di scacciarlo da una qualunque posizione, se lo desideri;
• \(N_k\subseteq K \), “l’intorno” della posizione \(k\in K\), cioé l’insieme delle posizioni sull’albero che risultano visibili per qualsiasi passero sia collocato nella posizione \(k\).

Tutte le possibili “assegnazioni” di posizioni a passeri possono essere rappresentate grazie all’introduzione, per \(i\in I \) and \(k \in K\), delle variabili binarie: \[x_{ik} = \left\{ \begin{array}{ll} 1 & \text{ se il passero } \ i \text{ assume la posizione}\ k.\\ 0 & \text{ altrimenti} \end{array} \right.\]

Ogni attribuzione di valore alle variabili \(x_{ik}\), per essere accettabile, deve assicurare che ad ogni passero sia assegnata una ed una sola posizione e che ogni posizione non possa essere occupata da piú di un passero. Quindi, sono accettabili tutte le configurazioni delle variabili \(x_{ik}\) che soddisfino il seguente sistema di equazioni e disequazioni:
\[\begin{aligned}{\displaystyle}&\sum_{k\in K}x_{ik}=1, &\,\,\,\, i\in I\ \ \ (1) \\ \\ &{\displaystyle}\sum_{i\in I}x_{ik}\leq 1,&\,\,\,\, k\in K \ \ \ (2)\\ \\ &x_{ik} \in \{0,1\},&i\in I, k\in K\ \ \ (3)\end{aligned}\]

Il sistema é costituito, per prima cosa, dalle \(n\) equazioni (1), una per ciascun passero. Si osservi che il soddisfacimento di ognuna di esse garantisce che al rispettivo passero sia assegnata esattamente una posizione tra le \(m\) disponibili. D’altro canto, il soddisfacimento del sistema di disequazioni (2), una per ciascuna delle posizioni disponibili, assicura che ognuna di esse possa essere occupata da non piú di un passero tra gli \(n\) presenti.

Quello che abbiamo fatto fino ad ora, però, è stata la semplice rappresentazione combinatoria delle possibili assegnazioni passero-posizione. Non abbiamo tenuto conto né delle preferenze per le posizioni né delle relazioni di forza associate ai passeri. Per farle entrare in gioco, definiamo, per ogni passero \(i \in I\), l’insieme

\[J_{i}=\{j | (i,j) \in \mathcal{R}\},\]

cioé l’insieme dei passeri che sono dominati da \(i\) (questo insieme puó, per qualche passero particolarmente sfortunato, essere vuoto!) e, per ogni coppia “passero \(i\)–posizione \(k\)” l’insieme

\[N_{k}^{i}=\{h | h \in N_k,~ q_{ih}\geq q_{ik}\},\]

cioé l’insieme delle posizioni nell’intorno della posizione \(k\) che, per il passero \(i\), sono almeno altrettanto gradite quanto la \(k\) stessa.

A questo punto aggiungiamo al sistema di equazioni e disequazioni definite prima anche il seguente insieme di disequazioni:

\[\begin{aligned} x_{ik}+x_{jh} \leq 1, &\,\,\,i \in I,\,\,k \in K,\,\, j\in J_i, \,\,h \in N_{k}^{i},~~~&\label{eqlin}\end{aligned}\ \ \ (4)\]

Il significato di queste disequazioni deriva dal seguente ragionamento. Osserviamo per prima cosa che, se \(x_{ik}=0\), l’equazione ([eqlin]) é banalmente verificata, indipendentemente dai valori di tutte le \(x_{jh}\). Se invece \(x_{ik}=1\), il soddisfacimento della stessa disequazione impone che sia \[x_{jh}=0, \,\,\, j\in J_i, \,\,\,h \in N_{k}^{i},\] e ció assicura che, se il passero \(i\) sta occupando la posizione \(k\), non ci sará nessuna passero \(j\) “dominato” da \(i\) che occupi una posizione \(h\) nell’intorno di \(k\) gradita ad \(i\) almeno quanto la posizione \(k\) stessa.

Chiameremo “assegnamento ripulsivo” qualsiasi attribuzione di valore alle variabili \(x_{ik}\) che soddisfi il sistema costituito dalle (1)–(4).

Supponendo che il modello descritto sia realistico, l’evidenza sperimentale (il silenzio della sera calato sull’albero) ci suggerisce che ogni sera, su ogni albero che sia popolato da passeri, la natura é in grado di raggiungere l’equilibrio che abbiamo cercato di descrivere. D’altra parte, se ci limitiamo agli aspetti matematici del problema, dobbiamo chiederci se il sistema (1)–(4) ammetta soluzione. In ^{[1 ]}M.Gaudioso, L. Moccia, M.F. Monaco, Repulsive assignment problem, Journal of Optimization Theory and Applications, 144, 2, p. 255–-273, 2010 viene dimostrato che decidere dell’esistenza di una soluzione per il problema (1)–(4) é un problema “difficile” (tecnicamente si dice che é un problema “NP completo”).

Per avere una idea della difficoltá si consideri ad esempio il caso in cui i passeri siano 100 e le posizioni disponibili 200. Supponiamo che, mediamente, da ciascuna posizione ne siano visibili altre dieci e che, ancora mediamente, per ogni passero ce ne siano 5 piú deboli di lui. Se volessimo formulare il nostro problema con questi “numeri”, avremmo a che fare con 20.000 variabili (le \(x_{ik}\)), 100 equazioni di tipo (1), 200 disequazioni di tipo (2) e circa un milione di disequazioni di tipo (4)!

Alla fine, le conclusioni possibili sono due: o in natura non esistono problemi “difficili”, oppure, se esistono, la natura è piú brava di noi, e di molto, a risolverli.

Manlio Gaudioso
Dipartimento di Ingegneria Informatica, Modellistica, Elettronica e Sistemistica
Università della Calabria