Teoria della complessità computazionale: differenze tra le versioni

Versione delle 15:49, 25 ott 2007

Versione attuale delle 19:49, 3 feb 2025

(106 versioni intermedie di 79 utenti non mostrate)

Riga 1:

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.

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.

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.

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

== Descrizione ==

=== Misurazione delle risorse ===

{{vedi anche|Stima asintotica}}

Per misurare lel'efficienza risorsedi computazionaliun richiestealgoritmo dallain soluzionemaniera diunivoca, unbisogna problemadefinire una metrica indipendente dalle tecnologie utilizzate, bisognaaltrimenti fareuno riferimentostesso adalgoritmo unpotrebbe modelloavere diefficienza calcolodiversa chea siaseconda ildella piùtecnologia possibilesulla generico,quale inè modoeseguito. chePer iquesto risultatimotivo ottenutisi sianousa riproducibilifare ancheriferimento suad altriun modellimodello di calcolo generico: la [[macchina di Turing]] soddisfa questo requisito. Infatti si dimostra che qualunqueQualunque 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. 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 dato un input ''<math>xf(n)</math>'' è il ''massimo'' numero di lunghezzapassi <math>n</math>,necessari laalla macchina per produrre il risultato su un input <math>Mx</math> producedi il risultato inlunghezza <math>f(n)</math> passi.

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 dato un input <math>x</math> di lunghezza <math>n</math>, la macchina <math>M</math> utilizza ''<math>f(n)</math>'' celle "temporanee" per effettuare la computazione.è Peril ''temporaneemassimo'' sinumero intendedi checelle lavisitate dimensionedurante dell'inputuna ecomputazione lasu dimensioneun dell'outputinput non<math>x</math> vengonodi conteggiate inlunghezza <math>f(n)</math>, oltre a quelle occupate dall'input.

Si osservi che, affinchéAffinché queste affermazioni siano valide, <math>f(n)</math> dev'essere una '''funzione di complessità propria''', cioè deve soddisfare le seguenti condizioni:

* dev'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 delle approssimazioni che permettonopermettano 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\ge> 0</math>, <math>n_0\ge 0</math>, <math>\forall n>n_0</math> <math>\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 simulazionesimulazioni, estrarre una formula che si approssimi adeguatamente lall'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>c\geforall 0</mathn>,n_0 \; g(n) <math>n_0\ge 0cf(n)</math>, per <math>\forallc n>n_0 0</math>, <math>g(n) n_0\ge cf(n)0</math>,. cioè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_deterministicaMacchina 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>.

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, <math>TIME(f(n))=TIME(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 per sono noti un 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 sono affermareaffermano 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 nondeterministiconon deterministico): pensarloe comenon per "non polinomiale" è sbagliato, anche se èper veromolti chedi tuttiessi glinon algoritmisi realizzabiliconoscono suche calcolatorialgoritmi fisicideterministici risolvonoche questiimpiegano problemi in[[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>

Riga 52 ⟶ 51:

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, però; ciò che è molto difficile diredeterminare è chese un certo algoritmo è il '''migliore possibile''' per un certodato 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 nelllnell'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>?''»

Quando il problema ''<math>P</math> è uguale a <math>NP</math>?'' è 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 <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.

QuandoIl il problema ''<math>P</math> è uguale a <math>NP</math>?''quesito è stato formulato nel [[1971]] e se ne intravedeva la soluzione dietro l'angolo, tuttavia dopo più di trentquarant'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 (matematica)|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>.

=== Riduzione in spazio logaritmico ===

In particolare, si sfrutta la riduzione ''in spazio logaritmico'' (simbolo <math>\le_{log}</math>, che permette di sfruttare proprietà [[insieme|insiemistiche]] molto utili:

Per dimostrare questa sorta di equivalenza, ci si riconduce alla teoria dei [[linguaggio formale (matematica)|linguaggi]], e si sfrutta il concetto di '''riduzione'''. Formalmente:

* '''transitività''', formalmente <math>(L_1 \le_{log} L_2) \and (L_2 \le_{log} L_3) \Rightarrow (L_1 \le_{log} L_3)</math>;

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

* '''chiusura''' delle classi di complessità, formalmente <math>(L \in C) \and (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à.

In particolare, si sfrutta la riduzione ''in spazio logaritmico'' (simbolo <math>\le_{log}</math>), che permette di sfruttare proprietà [[insieme|insiemistiche]] molto utili:

===NP-completezza===

* '''transitività''', formalmente <math>(L_1 \le_{log} L_2) \andland (L_2 \le_{log} L_3) \Rightarrow (L_1 \le_{log} L_3)</math>;

* '''chiusura''' delle classi di complessità, formalmente <math>(L \in C) \andland (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>. &Egrave;È 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 [[numerotest primo#Verifica_di_primalità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]], il problema di [[soddisfacibilità booleana]].

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.

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à==

== Approssimabilità ==

==Spin glass e K-solvibilità==

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

{{S sezione}}

== VociSpin correlateglass e K-solvibilità ==

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

*[[Complessità P e NP]]

*[[Classe di complessità]]

*[[Glossario delle classi di complessità]]

*[[Informatica]]

*[[Matematica]]

== Bibliografia ==

==Collegamenti esterni==

* {{en}} Peter Bürgisser, Michael Clausen, M. Amin Shokrollahi, ''Algebraic Complexity Theory'', Springer, 1997, ISBN 3-540-60582-7

*[http://arxiv.org/ftp/cs/papers/0309/0309020.pdf K-sat e spin glass], in [[lingua inglese|inglese]]

* {{en}} Mikhail J. Atallah (a cura di), ''Algorithms and Theory of Computation Handbook'', CRC Press, 1999, ISBN 0-8493-2649-4

*[http://www.ictp.trieste.it/~zecchina/SP/ Articoli di R.Zecchina a riguardo], in [[lingua inglese|inglese]]

== Voci correlate ==

{{classi di complessità}}

* [[Complessità P e NP]]

* [[Computazione]]

* [[Classe di complessità]]

* [[GlossarioLista 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 ==

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

{{interprogetto|preposizione=sulla}}

[[Categoria:Matematica per l'informatica]]

== Collegamenti esterni ==

{{Link AdQ|de}}

* {{Collegamenti esterni}}

* [httphttps://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:Complessità computazionale| Teoria della complessità computazionale| ]]

[[ar:نظرية التعقيد الحسابي]]

[[bn:গণনামূলক জটিলতা তত্ত্ব]]

[[cs:Teorie složitosti]]

[[de:Komplexitätstheorie]]

[[el:Θεωρία πολυπλοκότητας]]

[[en:Computational complexity theory]]

[[es:Complejidad computacional]]

[[fa:پیچیدگی محاسباتی]]

[[fr:Théorie de la complexité]]

[[he:סיבוכיות]]

[[hr:Računska teorija složenosti]]

[[ja:計算複雑性理論]]

[[ko:계산 복잡도 이론]]

[[lt:Algoritmų sudėtingumas]]

[[nl:Complexiteitstheorie]]

[[pl:Złożoność obliczeniowa]]

[[pt:Complexidade computacional]]

[[ru:Теория сложности вычислений]]

[[sr:Теорија комплексности]]

[[sv:Komplexitetsteori]]

[[th:ทฤษฎีความซับซ้อนในการคำนวณ]]

[[vi:Độ phức tạp thuật toán]]

[[zh:計算複雜性理論]]