Teoria della complessità computazionale

La teoria della complessità computazionale è una branca della teoria della computabilità che studia le risorse minime necessarie (principalmente tempo di calcolo e memoria) per la risoluzione di un problema. Con complessità di un algoritmo o efficienza di un algoritmo ci si riferisce dunque alle risorse di calcolo richieste. I problemi sono classificati in differenti classi di complessità, in base all'efficienza del migliore algoritmo noto in grado di risolvere quello specifico problema.

Una distinzione informale, ma di grande rilievo, è quella posta tra i cosiddetti problemi facili, di cui si conoscono algoritmi di risoluzione efficienti, e difficili, di cui gli unici algoritmi noti non sono efficienti. Ad esempio la maggior parte della crittografia moderna si fonda sull'esistenza di problemi ritenuti difficili; ha enorme rilevanza lo studio di tali problemi, poiché, qualora si dimostrasse l'esistenza di un algoritmo efficiente per un problema ritenuto difficile, i sistemi crittografici basati su di esso non sarebbero più sicuri.

Misurazione delle risorse

Per misurare l'efficienza di un algoritmo in maniera univoca, bisogna definire una metrica indipendente dalle tecnologie utilizzate, altrimenti uno stesso algoritmo potrebbe avere efficienza diversa a seconda della tecnologia sulla quale è eseguito. Per questo motivo si usa fare riferimento ad un modello di calcolo generico: la macchina di Turing. Qualunque modello di calcolo scelto (ad esempio la macchina RAM, ma si può parlare anche di computer reali), ai fini della classificazione dei problemi, si comporta come la macchina di Turing. La tesi di Church-Turing afferma, infatti, che la classe delle funzioni calcolabili coincide con quella delle funzioni calcolabili da una macchina di Turing.

Per quel che riguarda la misurazione della risorsa tempo, data una macchina di Turing $M$ , si dice che $M$ opera in tempo $f(n)$ se $f(n)$ è il massimo numero di passi necessari alla macchina per produrre il risultato su un input $x$ di lunghezza $n$ .

Per quel che riguarda la misurazione della risorsa spazio, data una macchina di Turing $M$ , si dice che $M$ opera in spazio $f(n)$ se $f(n)$ è il massimo numero di celle visitate durante una computazione su un input $x$ di lunghezza $n$ , oltre a quelle occupate dall'input.

Affinché queste affermazioni siano valide, $f(n)$ dev'essere una funzione di complessità propria, cioè deve soddisfare le seguenti condizioni:

deve essere monotona crescente;
deve essere calcolabile in tempo e spazio limitati dal valore della funzione stessa.

Poiché questo tipo di misurazione è molto dettagliata, quindi di solito difficilmente applicabile alla realtà, si introducono approssimazioni che permettano di operare su algoritmi più astratti. In particolare si ricorre alla notazione $O(\cdot )$ (O grande). Formalmente:

$f(n)=O(g(n))$ se $\exists (n_{0},c)$ tali che $c>0$ , $n_{0}\geq 0$ , $\forall n>n_{0}\quad f(n)\leq cg(n)$

La funzione $f(n)$ da un certo $n$ in poi cresce al più come la funzione $g(n)$ . Per fare un esempio, $n^{2}+2n+4\in O(n^{2})$ perché possiamo trovare una coppia di costanti $(n_{0},c)$ che soddisfano la condizione sopra. Si dice quindi che un algoritmo opera in tempo $O(f(n))$ se termina in un tempo proporzionale a $f(n)$ dato un input di dimensione $n$ .

Per valutare le prestazioni di un algoritmo, solo in parte legate alla classificazione di un problema, è utile distinguere alcuni casi: si considerano il caso ottimo, il caso peggiore e il caso medio.

Il caso ottimo è il caso in cui i dati sono i migliori dati possibili per l'algoritmo, cioè quelli che richiedono meno elaborazioni per essere trattati.
Il caso peggiore invece prevede i dati che richiedono il massimo numero di passi per l'algoritmo.
Il caso medio è il caso più utile da analizzare perché fornisce un reale indicatore della complessità dell'algoritmo, ma tendenzialmente è anche quello più complesso dato che spesso è difficile determinare quali sono i dati medi. A volte, per risolvere il problema del caso medio si preferisce eseguire molte simulazioni dell'algoritmo e poi, dai tempi ottenuti con le simulazioni, estrarre una formula che si approssimi adeguatamente all'andamento medio.

In questo ambito tornano dunque utili altre due misure, complementari della notazione O grande:

$g(n)=\Omega (f(n))$ se $\exists (n_{0},c)$ tali che $\forall n>n_{0}\;g(n)\geq cf(n)$ , per $c>0$ , $n_{0}\geq 0$ . Cioè $g(n)$ cresce non più lentamente di $f(n)$ ; questa notazione è utile per valutare il caso ottimo di un algoritmo: se un algoritmo è $\Omega (f(n))$ ("Omega di $f(n)$ ") significa che nel caso migliore richiede $f(n)$ passi per essere risolto.
$g(n)=\Theta (f(n))$ se $g(n)\in O(f(n))$ e $g(n)\in \Omega (f(n))$ , cioè $g(n)$ cresce altrettanto rapidamente di $f(n)$ . Se un algoritmo è $\Theta (f(n))$ ("Theta di $f(n)$ "), non ci sono variazioni significative di prestazioni tra il caso migliore e il caso peggiore.

Classi di complessità

Partendo dalla misurazione delle risorse computazionali si possono definire le classi di complessità:

la classe $TIME(f(n))$ è l'insieme dei problemi che ammettono una macchina di Turing che li risolve e che opera in tempo $O(f(n))$ .
La classe $NTIME(f(n))$ è l'insieme dei problemi che ammettono una macchina di Turing non deterministica che li risolve e che opera in tempo $O(f(n))$ .
La classe $SPACE(f(n))$ è l'insieme dei problemi che ammettono una macchina di Turing che li risolve e che opera in spazio $O(f(n))$ .
La classe $NSPACE(f(n))$ è l'insieme dei problemi che ammettono una macchina di Turing non deterministica che li risolve e che opera in spazio $O(f(n))$ .

Possiamo così definire le seguenti classi di complessità:

${\mbox{L}}={\mbox{SPACE}}(log(n))$
${\mbox{NL}}={\mbox{NSPACE}}(log(n))$
${\mbox{P}}=\cup _{k>0}{\mbox{TIME}}(n^{k})$ ; per risolvere i problemi appartenenti alle classi fin qui elencate sono noti algoritmi che terminano in tempo polinomiale rispetto alla dimensione dei dati.
${\mbox{NP}}=\cup _{k>0}{\mbox{NTIME}}(n^{k})$ ; per questi problemi sono noti algoritmi che terminano in un numero di passi polinomiale rispetto alla dimensione dei dati nel caso si possa utilizzare un numero indeterminato di macchine in parallelo, o nel caso si utilizzi una macchina di Turing non deterministica (come da definizione). Altre formulazioni equivalenti sono affermare che l'algoritmo termina in tempo polinomiale con l'"algoritmo di Gastone" (ogni volta che si deve fare una scelta, si indovina sempre la strada corretta), oppure che la verifica di una soluzione può essere effettuata in tempo polinomiale. La sigla NP sta per non-deterministic polinomial (polinomiale non deterministico) e non per "non polinomiale", anche se per molti di essi non si conoscono che algoritmi deterministici che impiegano tempo esponenziale rispetto a $n$ . A questa classe appartiene una gran quantità di problemi di interesse applicativo.
${\mbox{PSPACE}}=\cup _{k>0}{\mbox{SPACE}}(n^{k})$
${\mbox{NPSPACE}}=\cup _{k>0}{\mbox{NSPACE}}(n^{k})$
${\mbox{EXPTIME}}=\cup _{k>0}{\mbox{TIME}}(2^{n^{k}})$ ; per questi problemi sono noti solamente algoritmi che terminano in un numero di passi esponenziale rispetto alla dimensione dei dati, indipendentemente dal modello di calcolo.

Tra queste classi sono note le seguenti relazioni di equivalenza:

${\mbox{L}}\subseteq {\mbox{NL}}\subseteq {\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}={\mbox{NPSPACE}}\subseteq {\mbox{EXP}}$
${\mbox{L}}\subset {\mbox{PSPACE}}$
${\mbox{P}}\subset {\mbox{EXPTIME}}$

Altre relazioni non sono note.

L'implicazione pratica principale data da questa classificazione è la suddivisione in problemi che sappiamo risolvere in modo efficiente e in problemi che non sappiamo se possono essere risolti in modo efficiente. Infatti, calcolare il caso ottimo di un algoritmo di solito non è un'operazione troppo complicata; ciò che è molto difficile determinare è se un certo algoritmo è il migliore possibile per un dato problema. Dimostrazioni di questo tipo sono molto rare, la più nota è senz'altro quella riguardante l'ordinamento per confronto.

Data questa premessa, osserviamo che se sappiamo che un certo problema $\Pi \in {\mbox{NP}}$ , è in generale un errore dire $\Pi \notin {\mbox{P}}$ perché non è possibile dirlo, data anche l'inclusione non stretta di $P$ in ${\mbox{NP}}$ . Infatti, pur sapendo che ${\mbox{P}}\subseteq {\mbox{NP}}$ , non si sa se ${\mbox{P}}\subset {\mbox{NP}}$ o se ${\mbox{P}}={\mbox{NP}}$ , e questo è uno dei grandi problemi ancora aperti nell'informatica teorica, tanto da meritarsi un posto nei problemi per il millennio.

«Quando il problema $P$ è uguale a $NP$ ?»

Il quesito è stato formulato nel 1971 e se ne intravedeva la soluzione dietro l'angolo, tuttavia dopo più di quarant'anni di studi la questione è ancora aperta, ed essendo considerato uno dei problemi per il millennio la sua soluzione permetterebbe di vincere un milione di dollari USA (v. premio Clay). Gli unici passi avanti che si sono fatti riguardano la classificazione dei problemi. La strada che si è seguita è stata osservare che molti dei problemi che stavano nella classe $NP$ seguivano una stessa struttura: la costruzione della soluzione con un algoritmo non deterministico e la verifica della soluzione costruita con un algoritmo deterministico. Ci si chiedeva quindi se ci fosse un denominatore comune in questi problemi, e in effetti c'era: ci si è accorti che esistono dei problemi tali che un algoritmo per risolvere uno di questi problemi può essere convertito in un algoritmo per risolvere un qualunque problema NP. Questi problemi sono stati detti NP-difficili (NP-hard). Un problema NP-difficile potrebbe anche non stare in $NP$ , nel senso che la verifica della soluzione (o equivalentemente l'"algoritmo di Gastone") potrebbe richiedere un tempo più che polinomiale.

Riduzione in spazio logaritmico

Per dimostrare questa sorta di equivalenza, ci si riconduce alla teoria dei linguaggi, e si sfrutta il concetto di riduzione. Formalmente:

dati due linguaggi

L_{1}

e

L_{2}

, definiti rispettivamente sugli alfabeti

\Sigma _{1}

e

\Sigma _{2}

, una funzione

r:\Sigma _{1}^{*}\rightarrow \Sigma _{2}^{*}

è una riduzione dal linguaggio

L_{1}

al linguaggio

L_{2}

se

x\in L_{1}\iff r(x)\in L_{2}

.

In particolare, si sfrutta la riduzione in spazio logaritmico (simbolo $\leq _{log}$ ), che permette di sfruttare proprietà insiemistiche molto utili:

transitività, formalmente $(L_{1}\leq _{log}L_{2})\land (L_{2}\leq _{log}L_{3})\Rightarrow (L_{1}\leq _{log}L_{3})$ ;
chiusura delle classi di complessità, formalmente $(L\in C)\land (L'\leq _{log}L)\Rightarrow (L'\in C)$ , dove $C$ è una delle classi di complessità elencate sopra; in altre parole, qualunque linguaggio si riduca ad un elemento di $C$ , è anch'esso elemento di C;
completezza di elementi appartenenti alle classi, cioè $L$ è C-completo se $\forall L'\in C\Rightarrow L'\leq _{log}L$ , dove C è una delle classi di complessità elencate sopra: in altre parole, $L$ è C-completo se ogni elemento di $C$ si riduce ad esso.

La riduzione "in spazio logaritmico" è una riduzione che, oltre alle proprietà appena elencate, ha la caratteristica di essere calcolabile da una macchina di Turing che opera in spazio logaritmico, ed è grazie a questo che si dimostra la sua transitività.

NP-completezza

Alla luce di queste definizioni, si può dire che un problema $\Pi$ è NP-difficile se $\forall \Pi '\in NP\Rightarrow \Pi '\leq _{log}\Pi$ . I problemi NP-completi invece sono quei problemi $\Pi \in NP$ che sono anche NP-difficili, quindi tali che $\forall \Pi '\in NP\Rightarrow \Pi '\leq _{log}\Pi$ . È interessante notare che quasi tutti i problemi $NP$ (tranne quelli in $P$ ovviamente) sono anche NP-completi; l'unica eccezione nota, per ora, è l'isomorfismo di grafi, per il quale nessuno è ancora riuscito a dimostrare né la completezza, né l'eventuale appartenenza alla classe P. Fino a pochi anni fa, anche la verifica di primalità (dato un numero $n$ , dire se è primo oppure no) era un problema NP ma non NP-completo; tuttavia nel 2002 fu trovato un algoritmo che spostava il problema in P.

Esempi di problemi NP-completi sono il problema del commesso viaggiatore e il problema di soddisfacibilità booleana.

Con l'obiettivo di dimostrare l'uguaglianza $P=NP$ , si cominciò a cercare un algoritmo polinomiale per la soluzione di uno qualunque dei problemi NP-completi: questo avrebbe automaticamente fatto collassare tutta la classe di problemi $NP$ nella classe $P$ . Nessuno è riuscito a trovarne uno, né nessuno è mai riuscito a dimostrare che $P\subset NP$ attraverso un controesempio, sebbene molti esperti sospettino che questa sia la relazione tra le due classi.

(EN) Peter Bürgisser, Michael Clausen, M. Amin Shokrollahi, Algebraic Complexity Theory, Springer, 1997, ISBN 3-540-60582-7
(EN) Mikhail J. Atallah (a cura di), Algorithms and Theory of Computation Handbook, CRC Press, 1999, ISBN 0-8493-2649-4