Teoria della complessità computazionale

La Teoria della Complessità algoritmica o Teoria della Complessità computazionale si occupa della classificazione di problemi in base alle risorse computazionali (memoria occupata e tempo di calcolo) richieste per la loro soluzione.

Meno formalmente, si parla di complessità di un algoritmo riferendosi alle risorse computazionali da esso richieste.

Misurazione delle risorse

  Lo stesso argomento in dettaglio: Stima asintotica.

Per misurare le risorse computazionali richieste dalla soluzione di un problema, bisogna fare riferimento ad un modello di calcolo che sia il più possibile generico, in modo che i risultati ottenuti siano riproducibili anche su altri modelli di calcolo: la macchina di Turing soddisfa questo requisito. Infatti si dimostra che qualunque modello di calcolo scelto (come 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.

Per quel che riguarda la misurazione della risorsa tempo, data una macchina di Turing ${\displaystyle M}$ , si dice che ${\displaystyle M}$  opera in tempo ${\displaystyle f(n)}$  se dato un input ${\displaystyle x}$  di lunghezza ${\displaystyle n}$ , la macchina ${\displaystyle M}$  produce il risultato in ${\displaystyle f(n)}$  passi.

Per quel che riguarda la misurazione della risorsa spazio, data una macchina di Turing ${\displaystyle M}$ , si dice che ${\displaystyle M}$  opera in spazio ${\displaystyle f(n)}$  se dato un input ${\displaystyle x}$  di lunghezza ${\displaystyle n}$ , la macchina ${\displaystyle M}$  utilizza ${\displaystyle f(n)}$  celle "temporanee" per effettuare la computazione. Per temporanee si intende che la dimensione dell'input e la dimensione dell'output non vengono conteggiate in ${\displaystyle f(n)}$ .

Si osservi che, affinché queste affermazioni siano valide, ${\displaystyle f(n)}$  dev'essere una funzione di complessità propria, cioè deve soddisfare le seguenti condizioni:

• dev'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 delle approssimazioni che permettono di operare su algoritmi più astratti. In particolare si ricorre alla notazione ${\displaystyle O(\cdot )}$  (O grande). Formalmente:

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

La funzione ${\displaystyle f(n)}$  da un certo ${\displaystyle n}$  in poi cresce al più come la funzione ${\displaystyle g(n)}$ . Per fare un esempio, ${\displaystyle n^{2}+2n+4\in O(n^{2})}$  perché possiamo trovare una coppia di costanti ${\displaystyle (n_{0},c)}$  che soddisfano la condizione sopra. Si dice quindi che un algoritmo opera in tempo ${\displaystyle O(f(n))}$  se termina in un tempo proporzionale a ${\displaystyle f(n)}$  dato un input di dimensione ${\displaystyle 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 simulazione estrarre una formula che approssimi adeguatamente l'andamento medio.

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

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

Classi di complessità

  Lo stesso argomento in dettaglio: Classe di complessità.

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

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

Per tutte le classi definite sopra si dimostra che, grazie all'uso della macchina di Turing come modello di calcolo, l'utilizzo della notazione O grande all'interno della definizione non cambia il risultato. In questo modo, ad esempio, ${\displaystyle TIME(f(n))=TIME(O(f(n)))}$ .

Possiamo così definire le seguenti classi di complessità:

• ${\displaystyle {\mbox{L}}={\mbox{SPACE}}(log(n))\,\!}$ 
• ${\displaystyle {\mbox{NL}}={\mbox{NSPACE}}(log(n))\,\!}$ 
• ${\displaystyle {\mbox{P}}=\cup _{k>0}{\mbox{TIME}}(n^{k})}$ ; per risolvere i problemi appartenenti alle classi fin qui elencate per sono noti un algoritmi che terminano in tempo polinomiale rispetto alla dimensione dei dati.
• ${\displaystyle {\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 nondeterministico): pensarlo come "non polinomiale" è sbagliato, anche se è vero che tutti gli algoritmi realizzabili su calcolatori fisici risolvono questi problemi in tempo esponenziale rispetto a ${\displaystyle n}$ . A questa classe appartiene una gran quantità di problemi di interesse applicativo.
• ${\displaystyle {\mbox{PSPACE}}=\cup _{k>0}{\mbox{SPACE}}(n^{k})}$ 
• ${\displaystyle {\mbox{NPSPACE}}=\cup _{k>0}{\mbox{NSPACE}}(n^{k})}$ 
• ${\displaystyle {\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:

${\displaystyle {\mbox{L}}\subseteq {\mbox{NL}}\subseteq {\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}={\mbox{NPSPACE}}\subseteq {\mbox{EXP}}}$ 
${\displaystyle {\mbox{L}}\subset {\mbox{PSPACE}}}$ 
${\displaystyle {\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, però ciò che è molto difficile dire è che un certo algoritmo è il migliore possibile per un certo 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 ${\displaystyle \Pi \in {\mbox{NP}}}$ , è in generale un errore dire ${\displaystyle \Pi \notin {\mbox{P}}}$  perché non è possibile dirlo, data anche l'inclusione non stretta di ${\displaystyle P}$  in ${\displaystyle {\mbox{NP}}}$ . Infatti, pur sapendo che ${\displaystyle {\mbox{P}}\subseteq {\mbox{NP}}}$ , non si sa se ${\displaystyle {\mbox{P}}\subset {\mbox{NP}}}$  o se ${\displaystyle {\mbox{P}}={\mbox{NP}}\,\!}$ , e questo è uno dei grandi problemi ancora aperti nelll'informatica teorica, tanto da meritarsi un posto nei problemi per il millennio.

Problemi NP-completi

Quando il problema ${\displaystyle P}$  è uguale a ${\displaystyle NP}$ ? è stato formulato nel 1971 se ne intravedeva la soluzione dietro l'angolo, tuttavia dopo più di trent'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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle L_{1}}$  e ${\displaystyle L_{2}}$ , definiti rispettivamente sugli alfabeti ${\displaystyle \Sigma _{1}}$  e ${\displaystyle \Sigma _{2}}$ , una funzione ${\displaystyle r:\Sigma _{1}^{*}\rightarrow \Sigma _{2}^{*}}$  è una riduzione dal linguaggio ${\displaystyle L_{1}}$  al linguaggio ${\displaystyle L_{2}}$  se ${\displaystyle x\in L_{1}\iff r(x)\in L_{2}}$ .

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

• transitività, formalmente ${\displaystyle (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 ${\displaystyle (L\in C)\land (L'\leq _{log}L)\Rightarrow (L'\in C)}$ , dove ${\displaystyle C}$  è una delle classi di complessità elencate sopra; in altre parole, qualunque linguaggio si riduca ad un elemento di ${\displaystyle C}$ , è anch'esso elemento di C;
• completezza di elementi appartenenti alle classi, cioè ${\displaystyle L}$  è C-completo se ${\displaystyle \forall L'\in C\Rightarrow L'\leq _{log}L}$ , dove C è una delle classi di complessità elencate sopra: in altre parole, ${\displaystyle L}$  è C-completo se ogni elemento di ${\displaystyle 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

  Lo stesso argomento in dettaglio: NP-Completo.

Alla luce di queste definizioni, si può dire che un problema ${\displaystyle \Pi }$  è NP-difficile se ${\displaystyle \forall \Pi '\in NP\Rightarrow \Pi '\leq _{log}\Pi }$ . I problemi NP-completi invece sono quei problemi ${\displaystyle \Pi \in NP}$  che sono anche NP-difficili, quindi tali che ${\displaystyle \forall \Pi '\in NP\Rightarrow \Pi '\leq _{log}\Pi }$ . È interessante notare che quasi tutti i problemi ${\displaystyle NP}$  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 ${\displaystyle 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, il problema di soddisfacibilità booleana.

Con l'obiettivo di dimostrare l'uguaglianza ${\displaystyle 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 ${\displaystyle NP}$  nella classe ${\displaystyle P}$ . Nessuno è riuscito a trovarne uno, né nessuno è mai riuscito a dimostrare che ${\displaystyle P\subset NP}$  attraverso un controesempio, sebbene molti esperti sospettino che questa sia la relazione tra le due classi.

Approssimabilità

Spin glass e K-solvibilità

Voci correlate

• Complessità P e NP
• Classe di complessità
• Glossario delle classi di complessità
• Informatica
• Matematica
• Teoria della complessità algoritmica

Collegamenti esterni

• K-sat e spin glass, in inglese
• Articoli di R.Zecchina a riguardo, in inglese

Template:Link AdQ