Teoria della complessità computazionale

Da Wikipedia, l'enciclopedia libera.

In informatica, la teoria della complessità algoritmica o 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. I problemi vengono così classificati in differenti classi di complessità, a seconda di quanto il migliore algoritmo di risoluzione noto sia efficiente.

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. La maggior parte della crittografia moderna si fonda sull'esistenza di problemi ritenuti difficili; ciò pone un'enorme rilevanza allo 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.

Con complessità di un algoritmo o efficienza di un algoritmo ci si riferisce alle risorse di calcolo da esso richieste.

Indice

1 Misurazione delle risorse
2 Classi di complessità
3 Problemi NP-completi
- 3.1 Riduzione in spazio logaritmico
- 3.2 NP-completezza
4 Approssimabilità
5 Spin glass e K-solvibilità
6 Voci correlate
7 Collegamenti esterni

[modifica] Misurazione delle risorse

Per approfondire, vedi la voce Stima asintotica.

Per misurare l'efficienza di un algoritmo in maniera univoca, bisogna definire una metrica che sia indipendente dalle tecnologie utilizzate, altrimenti uno stesso algoritmo potrebbe avere efficienza diversa a seconda della tecnologia sulla quale viene eseguito. Per questo motivo si usa fare riferimento ad un modello di calcolo generico: la macchina di Turing. 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 $M$ , si dice che $M$ opera in tempo $f (n)$ se dato un input $x$ di lunghezza $n$ , la macchina $M$ produce il risultato in $f (n)$ passi.

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 dato un input $x$ di lunghezza $n$ , la macchina $M$ utilizza $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 $f (n)$ .

Si osservi che, affinché queste affermazioni siano valide, $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 $O(\cdot)$ (O grande). Formalmente:

f (n) = O (g (n))

se $\exists (n_{0}, c)$ tali che $c\ge 0$ , $n_0\ge 0$ , $\forall n>n_0$ $f(n) \le c g(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 simulazione estrarre una formula che approssimi adeguatamente l'andamento medio.

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

$g (n) = Ω(f (n))$ se $\exists (n_{0}, c)$ tali che $c\ge 0$ , $n_0\ge 0$ , $\forall n>n_0$ $g(n) \ge cf(n)$ , cioè $g (n)$ cresce non più lentamente di $f (n)$ ; questa notazione è utile per valutare il caso ottimo di un algoritmo: se un algoritmo è $Ω(f (n))$ ("Omega di $f (n)$ ") significa che nel caso migliore richiede $f (n)$ passi per essere risolto.
$g (n) = Θ(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 è $Θ(f (n))$ ("Theta di $f (n)$ "), non ci sono variazioni significative di prestazioni tra il caso migliore e il caso peggiore.

[modifica] Classi di complessità

Per approfondire, vedi la voce Classe di complessità.

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

la classe $T I M E (f (n))$ è l'insieme dei problemi che ammettono una macchina di Turing che li risolve e che opera in tempo $f (n)$ .
La classe $N T I M E (f (n))$ è l'insieme dei problemi che ammettono una macchina di Turing non deterministica che li risolve e che opera in tempo $f (n)$ .
La classe $S P A C E (f (n))$ è l'insieme dei problemi che ammettono una macchina di Turing che li risolve e che opera in spazio $f (n)$ .
La classe $N S P A C E (f (n))$ è l'insieme dei problemi che ammettono una macchina di Turing non deterministica che li risolve e che opera in spazio $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, $T I M E (f (n)) = T I M E (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 per sono noti un 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 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 $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:

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 $\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 $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 nelll'informatica teorica, tanto da meritarsi un posto nei problemi per il millennio.

[modifica] Problemi NP-completi

Quando il problema $P$ è uguale a $N P$ ? è 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 $N P$ 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 $N P$ , nel senso che la verifica della soluzione (o equivalentemente l'"algoritmo di Gastone") potrebbe richiedere un tempo più che polinomiale.

[modifica] 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

L 2

, definiti rispettivamente sugli alfabeti

Σ 1

Σ 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 $\le_{log}$ , che permette di sfruttare proprietà insiemistiche molto utili:

transitività, formalmente $(L_1 \le_{log} L_2) \and (L_2 \le_{log} L_3) \Rightarrow (L_1 \le_{log} L_3)$ ;
chiusura delle classi di complessità, formalmente $(L \in C) \and (L' \le_{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' \le_{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à.

[modifica] NP-completezza

Per approfondire, vedi la voce NP-Completo.

Alla luce di queste definizioni, si può dire che un problema $Π$ è NP-difficile se $\forall \Pi' \in NP \Rightarrow \Pi' \le_{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' \le_{log} \Pi$ . È interessante notare che quasi tutti i problemi $N P$ 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, il problema di soddisfacibilità booleana.

Con l'obiettivo di dimostrare l'uguaglianza $P = N P$ , 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 $N P$ 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.

[modifica] Approssimabilità

[modifica] Spin glass e K-solvibilità

Questa sezione è solo un abbozzo. Se puoi, contribuisci ad ampliarla.

[modifica] Voci correlate

[modifica] Collegamenti esterni

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

Classi di complessità (elenco)
P • NP • co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • EXPSPACE • PR • RE • Co-RE • RE-C • Co-RE-C • R • BQP • BPP • RP • ZPP • PCP • IP • PH

Teoria della complessità computazionale

Da Wikipedia, l'enciclopedia libera.

Indice

[modifica] Misurazione delle risorse

[modifica] Classi di complessità

[modifica] Problemi NP-completi

[modifica] Riduzione in spazio logaritmico

[modifica] NP-completezza

[modifica] Approssimabilità

[modifica] Spin glass e K-solvibilità

[modifica] Voci correlate

[modifica] Collegamenti esterni

Views

Navigazione

comunità

Ricerca

Altre lingue