Classe di complessità

Da Wikipedia, l'enciclopedia libera.

Nella teoria della complessità computazionale, una classe di complessità è un insieme di problemi di una certa complessità. Un esempio tipico di definizione di classe di complessità ha la forma:

l'insieme di problemi che, se esiste la soluzione, possono essere risolti da una macchina astratta M usando O(f(n)) della risorsa R, con n dimensione dell'input

Ad esempio, la classe NP è l'insieme dei problemi di decisione che possono essere risolti da una macchina di Turing non deterministica in tempo polinomiale, mentre la classe P è l'insieme dei problemi di decisione che possono essere risolti da una macchina di Turing deterministica in tempo polinomiale. Alcune classi di complessità sono insiemi di problemi costruttivi (cioè che richiedono di calcolare una funzione, e non di rispondere SÌ o NO), come ad esempio FP.

Molte classi di complessità possono essere caratterizzate in termini della logica matematica necessaria ad esprimerle; vedi complessità descrittiva.

Gli assiomi di Blum possono essere usati per definire classi di complessità senza riferirsi ad un modello computazionale concreto.

Relazioni tra classi di complessità[modifica | modifica wikitesto]

La seguente tabella mostra alcune classi di problemi (o di linguaggi) che sono considerate nella teoria della complessità. Se la classe X è un sottoinsieme stretto di Y, allora X è rappresentata sotto ad Y, con una linea continua che li connette. Se X è un sottoinsieme, ma non si sa se X e Y sono insiemi uguali, allora la linea è tratteggiata. Tecnicamente, la suddivisione tra problemi solubili e insolubili appartiene più alla teoria della calcolabilità, ma aiuta a vedere in prospettiva le classi di complessità.

Problemi di decisione
SolidLine.png SolidLine.png
Tipo 0 (Ricorsivamente enumerabili)
Indecidibili
SolidLine.png
Decidibile
SolidLine.png
EXPSPACE
DottedLine.png
EXPTIME
DottedLine.png
PSPACE
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
Tipo 1 (dipendente dal contesto)
SolidLine.png DottedLine.png DottedLine.png DottedLine.png
PSPACE-Completi
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png
Co-NP
DottedLine.png
NP
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png DottedLine.png
BPP
BQP
NP-Completi
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png
P
SolidLine.png SolidLine.png DottedLine.png DottedLine.png
SolidLine.png
NC
P-Completi
SolidLine.png SolidLine.png
Tipo 2 (libero dal contesto)
SolidLine.png
Tipo 3 (Regolare)

Voci correlate[modifica | modifica wikitesto]

Bibliografia[modifica | modifica wikitesto]

  • The Complexity Zoo: una lista di classi di complessità, come riferimento per gli esperti.
  • Diagram by Neil Immerman mostra la gerarchia delle classi di complessità e come queste si combinano tra di loro.
  • Michael Garey, and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. Il riferimento standard per i problemi NP-Completi.