Visualizza wikitesto di Teoria della complessità computazionale

La '''teoria della complessità computazionale''' è una branca della [[teoria della computabilità]] che studia le [[risorsa informatica|risorse]] minime necessarie (principalmente tempo di calcolo e [[memoria informatica|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 ''[[classe di complessità|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.

== Descrizione ==
=== Misurazione delle risorse ===
{{vedi anche|Stima asintotica}}
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 <math>M</math>, si dice che ''<math>M</math> opera in tempo <math>f(n)</math>'' se ''<math>f(n)</math>'' è il ''massimo'' numero di passi necessari alla macchina per produrre il risultato su un input <math>x</math> di lunghezza <math>n</math>.

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

Affinché queste affermazioni siano valide, <math>f(n)</math> dev'essere una ''funzione di complessità propria'', cioè deve soddisfare le seguenti condizioni:
* deve essere [[funzione monotona|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 [[algoritmo|algoritmi]] più astratti. In particolare si ricorre alla notazione <math>O(\cdot)</math> (''[[O-grande|O grande]]''). Formalmente:

<math>f(n) = O(g(n))</math> se <math>\exists (n_{0}, c)</math> tali che <math>c> 0</math>, <math>n_0\ge 0</math>, <math>\forall n>n_0 \quad  f(n) \le c g(n)</math>

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

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'':

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

=== Classi di complessità ===
{{Vedi anche|Classe di complessità}}
Partendo dalla misurazione delle risorse computazionali si possono definire le classi di complessità:
* la classe <math>TIME(f(n))</math> è l'insieme dei problemi che ammettono una macchina di Turing che li risolve e che opera in tempo  <math>O(f(n))</math>.
* La classe <math>NTIME(f(n))</math> è l'insieme dei problemi che ammettono una [[Macchina di Turing#Macchina di Turing non deterministica|macchina di Turing ''non deterministica'']] che li risolve e che opera in tempo  <math>O(f(n))</math>.
* La classe <math>SPACE(f(n))</math> è l'insieme dei problemi che ammettono una macchina di Turing che li risolve e che opera in spazio  <math>O(f(n))</math>.
* La classe <math>NSPACE(f(n))</math> è l'insieme dei problemi che ammettono una macchina di Turing ''non deterministica'' che li risolve e che opera in spazio  <math>O(f(n))</math>.

Possiamo così definire le seguenti classi di complessità:
* <math>\mbox{L} = \mbox{SPACE}(log(n))</math>
* <math>\mbox{NL} = \mbox{NSPACE}(log(n))</math>
* <math>\mbox{P} = \cup_{k>0} \mbox{TIME}(n^k)</math>; per risolvere i problemi appartenenti alle classi fin qui elencate sono noti algoritmi che terminano in tempo polinomiale rispetto alla dimensione dei dati.
* <math>\mbox{NP} = \cup_{k>0} \mbox{NTIME}(n^k)</math>; 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 affermano 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 [[Complessità temporale|tempo esponenziale]] rispetto a <math>n</math>. A questa classe appartiene una gran quantità di problemi di interesse applicativo.
* <math>\mbox{PSPACE} = \cup_{k>0} \mbox{SPACE}(n^k)</math>
* <math>\mbox{NPSPACE} = \cup_{k>0} \mbox{NSPACE}(n^k)</math>
* <math>\mbox{EXPTIME} = \cup_{k>0} \mbox{TIME}(2^{n^k})</math>; 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:
* <math>\mbox{L} \subseteq \mbox{NL} \subseteq \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PSPACE} = \mbox{NPSPACE} \subseteq \mbox{EXP}</math>
* <math>\mbox{L} \subset \mbox{PSPACE}</math>
* <math>\mbox{P} \subset \mbox{EXPTIME}</math>

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'[[algoritmo di ordinamento|ordinamento]] per confronto.

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

== Problemi ''NP-completi'' ==
«Quando il problema ''<math>P</math> è uguale a <math>NP</math>?''»

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 <math>NP</math> 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 <math>NP</math>, 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 [[linguaggio formale|linguaggi]], e si sfrutta il concetto di '''riduzione'''. Formalmente:
:dati due linguaggi <math>L_1</math> e <math>L_2</math>, definiti rispettivamente sugli alfabeti <math>\Sigma_1</math> e <math>\Sigma_2</math>, una funzione <math>r:\Sigma_1^* \rightarrow \Sigma_2^*</math> è una ''riduzione'' dal linguaggio <math>L_1</math> al linguaggio <math>L_2</math> se <math>x \in L_1 \iff r(x) \in L_2</math>.

In particolare, si sfrutta la riduzione ''in spazio logaritmico'' (simbolo <math>\le_{log}</math>), che permette di sfruttare proprietà [[insieme|insiemistiche]] molto utili:
* ''transitività'', formalmente <math>(L_1 \le_{log} L_2) \land (L_2 \le_{log} L_3) \Rightarrow (L_1 \le_{log} L_3)</math>;
* ''chiusura'' delle classi di complessità, formalmente <math>(L \in C) \land (L' \le_{log} L) \Rightarrow (L' \in C)</math>, dove <math>C</math> è una delle classi di complessità elencate sopra; in altre parole, qualunque linguaggio si riduca ad un elemento di <math>C</math>, è anch'esso elemento di C;
* ''completezza'' di elementi appartenenti alle classi, cioè <math>L</math> è C-completo se <math>\forall L' \in C \Rightarrow L' \le_{log} L</math>, dove C è una delle classi di complessità elencate sopra: in altre parole, <math>L</math> è C-completo se ogni elemento di <math>C</math> 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 ===
{{vedi anche|NP-Completo}}
Alla luce di queste definizioni, si può dire che un problema <math>\Pi</math> è ''NP-difficile'' se <math>\forall \Pi' \in NP \Rightarrow \Pi' \le_{log} \Pi</math>. I problemi ''NP-completi'' invece sono quei problemi <math>\Pi \in NP</math> che sono anche NP-difficili, quindi tali che <math>\forall \Pi' \in NP \Rightarrow \Pi' \le_{log} \Pi</math>. È interessante notare che quasi tutti i problemi <math>NP</math> (tranne quelli in <math>P</math> ovviamente) sono anche NP-completi; l'unica eccezione nota, per ora, è l'[[isomorfismo]] di [[grafo|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 [[test di primalità|verifica di primalità]] (dato un numero <math>n</math>, 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 <math>P=NP</math>, 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 <math>NP</math> nella classe <math>P</math>. Nessuno è riuscito a trovarne uno, né nessuno è mai riuscito a dimostrare che <math>P \subset NP</math> attraverso un [[controesempio]], sebbene molti esperti sospettino che questa sia la relazione tra le due classi.

== Approssimabilità ==
{{...|informatica|arg2=matematica}}

== Spin glass e K-solvibilità ==
{{...|informatica|arg2=matematica}}

== Bibliografia ==
* {{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

== Voci correlate ==
* [[Complessità P e NP]]
* [[Computazione]]
* [[Classe di complessità]]
* [[Lista delle classi di complessità]]
* [[Teoria della complessità algoritmica]]
* [[Teoria della computazione]]
* [[Teoria della computabilità]]
* [[Teoria della computabilità effettiva]]
* [[Teorema dello speedup di Blum]]
* [[Worst-case execution time]]

== Altri progetti ==
{{interprogetto|preposizione=sulla}}

== Collegamenti esterni ==
* {{Collegamenti esterni}}
* [https://arxiv.org/ftp/cs/papers/0309/0309020.pdf K-sat e spin glass], in [[lingua inglese|inglese]]

{{classi di complessità}}
{{Ordinamento}}
{{Controllo di autorità}}
{{Portale|informatica|matematica}}

[[Categoria:Teoria della complessità computazionale| ]]