|
[[File:Complexity subsets pspace.svg|miniatura|Rappresentazione delle varie classi di complessità|300x300px]]
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:
Nella [[teoria della complessità computazionale]], una '''classe di complessità''' è un [[insieme]] di [[Problema computazionale|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 <math>O(f(n))</math> della risorsa R, con <math>n</math> dimensione dell'input
Ad esempio, la classe [[NP (complessità)|'''NP''']] è l'insieme dei problemi di decisione che possono essere risolti da una [[macchina di Turing#Macchina di Turing non deterministica|macchina di Turing non deterministica]] in tempo polinomiale, mentre la classe [[P (complessità)|'''P''']] è l'insieme dei problemi di decisione che possono essere risolti da una [[macchina di Turing]] deterministica in spaziotempo 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 (complessità)|'''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à ==
La seguente tabella mostra alcune classi di problemi (o di linguaggi, o grammatiche) 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à.
{| cellpadding="0" cellspacing="0" border="0" align="center"
|- align="center"
| colspan=2 |
| colspan=4 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
| align="center" | [[Problema decisionale|Problemi di decisione]]
|}
|- align="center"
| colspan=2 |
| [[File:solidLine.png]]
| colspan=2 |
| [[File:solidLine.png]]
|- align="center"
| colspan=3 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
| align="center" | [[Linguaggio ricorsivamente enumerabile|Tipo 0 (Ricorsivamente enumerabili)]]
|}
|
| colspan=4 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
| align="center" | [[Problema decisionale|Indecidibili]]
|}
|- align="center"
| colspan=3 | [[File:solidLine.png]]
|- align="center"
| colspan=3 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
| align="center" | [[Linguaggio ricorsivo|Decidibile]]
|}
|- align="center"
| colspan=3 | [[File:solidLine.png]]
|- align="center"
| colspan=3 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
| align="center" | [[EXPSPACE]]
|}
|- align="center"
| colspan=3 | [[File:dottedLine.png]]
|- align="center"
| colspan=3 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
| align="center" | [[EXPTIME]]
|}
|- align="center"
| colspan=3 | [[File:dottedLine.png]]
|- align="center"
| colspan=8 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
| align="center" | [[PSPACE]]
|}
|- align="center"
| [[File:solidLine.png]]
| width=40 | [[File:solidLine.png]]
| [[File:dottedLine.png]]
| [[File:dottedLine.png]]
|
| [[File:dottedLine.png]]
|
| [[File:dottedLine.png]]
|- align="center"
|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
| align="center" | [[Linguaggio dipendente dal contesto|Tipo 1 (dipendente dal contesto)]]
|}
| [[File:solidLine.png]]
| [[File:dottedLine.png]]
| border="1" | [[File:dottedLine.png]]
|
| [[File:dottedLine.png]]
|
| colspan=1 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
| align="center" | [[PSPACE-completo|PSPACE-Completi]]
|}
|- align="center"
| [[File:solidLine.png]]
| [[File:solidLine.png]]
| [[File:dottedLine.png]]
| [[File:dottedLine.png]]
|
| [[File:dottedLine.png]]
|- align="center"
| [[File:solidLine.png]]
| [[File:solidLine.png]]
|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
| align="center" | [[Co-NP]]
|}
| [[File:dottedLine.png]]
|
| colspan=3 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
| align="center" | [[NP (complessità)|NP]]
|}
|- align="center"
| [[File:solidLine.png]]
| [[File:solidLine.png]]
| [[File:dottedLine.png]]
| [[File:dottedLine.png]]
|
| [[File:dottedLine.png]]
|
| [[File:dottedLine.png]]
|- align="center"
| [[File:solidLine.png]]
| [[File:solidLine.png]]
| [[File:dottedLine.png]]
|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
| align="center" | [[BPP (complessità)|BPP]]
|}
| width=10 |
|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
| align="center" | [[BQP (complessità)|BQP]]
|}
| width=10 |
|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
| align="center" | [[NP-Completo|NP-Completi]]
|}
|- align="center"
| [[File:solidLine.png]]
| [[File:solidLine.png]]
| [[File:dottedLine.png]]
| [[File:dottedLine.png]]
|
| [[File:dottedLine.png]]
|- align="center"
| [[File:solidLine.png]]
| [[File:solidLine.png]]
| colspan=6 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
| align="center" | [[P (complessità)|P]]
|}
|- align="center"
| [[File:solidLine.png]]
| [[File:solidLine.png]]
| [[File:dottedLine.png]]
| colspan=4 |
| [[File:dottedLine.png]]
|- align="center"
| [[File:solidLine.png]]
| colspan=2 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
| align="center" | [[NC (complessità)|NC]]
|}
| colspan=4 |
|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
| align="center" | [[P-Completo|P-Completi]]
|}
|- align="center"
| [[File:solidLine.png]]
| colspan=2 | [[File:solidLine.png]]
|- align="center"
| colspan=3 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
| align="center" | [[Linguaggio libero dal contesto|Tipo 2 (libero dal contesto)]]
|}
|- align="center"
| colspan=3 | [[File:solidLine.png]]
|- align="center"
| colspan=3 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
| align="center" | [[Linguaggio regolare|Tipo 3 (Regolare)]]
|}
|}
== Bibliografia ==
* [https://web.archive.org/web/20100726082118/http://qwiki.stanford.edu/wiki/Complexity_Zoo The Complexity Zoo]: una lista di classi di complessità, come riferimento per gli esperti.
* [https://web.archive.org/web/20160416021243/https://people.cs.umass.edu/~immerman/complexity_theory.html Diagram] by [[Neil Immerman]] mostra la gerarchia delle classi di complessità e come queste si combinano tra di loro.
* [[Garey, Michael R.|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-Completo|NP-Completi]].
== Voci correlate ==
<table cellpadding="0" cellspacing="0" border="0" align="center">
* [[Lista delle classi di complessità]]
<tr align="center">
<td colspan=2></td>
<td colspan=4><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">[[Problemi di decisione]]</td></tr></table></td>
</tr>
<tr align="center">
<td colspan=2></td>
<td>[[Immagine:solidLine.png]]</td>
<td colspan=2></td>
<td>[[Immagine:solidLine.png]]</td>
</tr>
<tr align="center">
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">[[Linguaggio ricorsivamente enumerabile|Tipo 0 (Ricorsivamente enumerabili)]]</td></tr></table></td>
<td></td>
<td colspan=4><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">[[Problemi di decisione|Indecidibili]]</td></tr></table></td>
</tr>
<tr align="center">
<td colspan=3>[[Immagine:solidLine.png]]</td>
</tr>
<tr align="center">
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">[[Linguaggio ricorsivo|Decidibile]]</td></tr></table></td>
</tr>
<tr align="center">
<td colspan=3>[[Immagine:solidLine.png]]</td>
</tr>
<tr align="center">
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[EXPSPACE]]</td></tr></table></td>
</tr>
<tr align="center">
<td colspan=3>[[Immagine:dottedLine.png]]</td>
</tr>
<tr align="center">
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[EXPTIME]]</td></tr></table></td>
</tr>
<tr align="center">
<td colspan=3>[[Immagine:dottedLine.png]]</td>
</tr>
<tr align="center">
<td colspan=8><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[PSPACE]]</td></tr></table></td>
</tr>
<tr align="center">
<td>[[Immagine:solidLine.png]]</td>
<td width=40>[[Immagine:solidLine.png]]</td>
<td>[[Immagine:dottedLine.png]]</td>
<td>[[Immagine:dottedLine.png]]</td>
<td></td>
<td>[[Immagine:dottedLine.png]]</td>
<td></td>
<td>[[Immagine:dottedLine.png]]</td>
</tr>
<tr align="center">
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">[[Grammatica sensibile al contesto|Tipo 1 (sensibile al contesto)]]</td></tr></table></td>
<td>[[Immagine:solidLine.png]]</td>
<td>[[Immagine:dottedLine.png]]</td>
<td border="1">[[Immagine:dottedLine.png]]</td>
<td></td>
<td>[[Immagine:dottedLine.png]]</td>
<td></td>
<td colspan=1><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[PSPACE-Completo|PSPACE-Completi]]</td></tr></table></td>
</tr>
<tr align="center">
<td>[[Immagine:solidLine.png]]</td>
<td>[[Immagine:solidLine.png]]</td>
<td>[[Immagine:dottedLine.png]]</td>
<td>[[Immagine:dottedLine.png]]</td>
<td></td>
<td>[[Immagine:dottedLine.png]]</td>
</tr>
<tr align="center">
<td>[[Immagine:solidLine.png]]</td>
<td>[[Immagine:solidLine.png]]</td>
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[Co-NP]]</td></tr></table></td>
<td>[[Immagine:dottedLine.png]]</td>
<td></td>
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[NP (complessità)|NP]]</td></tr></table></td>
</tr>
<tr align="center">
<td>[[Immagine:solidLine.png]]</td>
<td>[[Immagine:solidLine.png]]</td>
<td>[[Immagine:dottedLine.png]]</td>
<td>[[Immagine:dottedLine.png]]</td>
<td></td>
<td>[[Immagine:dottedLine.png]]</td>
<td></td>
<td>[[Immagine:dottedLine.png]]</td>
</tr>
<tr align="center">
<td>[[Immagine:solidLine.png]]</td>
<td>[[Immagine:solidLine.png]]</td>
<td>[[Immagine:dottedLine.png]]</td>
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[BPP (complessità)|BPP]]</td></tr></table></td>
<td width=10></td>
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[BQP]]</td></tr></table></td>
<td width=10></td>
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[NP-Completo|NP-Completi]]</td></tr></table></td>
</tr>
<tr align="center">
<td>[[Immagine:solidLine.png]]</td>
<td>[[Immagine:solidLine.png]]</td>
<td>[[Immagine:dottedLine.png]]</td>
<td>[[Immagine:dottedLine.png]]</td>
<td></td>
<td>[[Immagine:dottedLine.png]]</td>
</tr>
<tr align="center">
<td>[[Immagine:solidLine.png]]</td>
<td>[[Immagine:solidLine.png]]</td>
<td colspan=6><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[P (complessità)|P]]</td></tr></table></td>
</tr>
<tr align="center">
<td>[[Immagine:solidLine.png]]</td>
<td>[[Immagine:solidLine.png]]</td>
<td>[[Immagine:dottedLine.png]]</td>
<td colspan=4></td>
<td>[[Immagine:dottedLine.png]]</td>
</tr>
<tr align="center">
<td>[[Immagine:solidLine.png]]</td>
<td colspan=2><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[NC (complessità)|NC]]</td></tr></table></td>
<td colspan=4></td>
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[P-Completo|P-Completi]]</td></tr></table></td>
</tr>
<tr align="center">
<td>[[Immagine:solidLine.png]]</td>
<td colspan=2>[[Immagine:solidLine.png]]</td>
</tr>
<tr align="center">
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">[[Grammatica libera dal contesto|Tipo 2 (libera dal contesto)]]</td></tr></table></td>
</tr>
<tr align="center">
<td colspan=3>[[Immagine:solidLine.png]]</td>
</tr>
<tr align="center">
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">[[Grammatica regolare|Tipo 3 (Regolare)]]</td></tr></table></td>
</tr>
</table>
==Voci correlate==
* [[Glossario delle classi di complessità]]
* [[Teoria della calcolabilità]]
* [[Teoria della complessità computazionale]]
== Collegamenti esterni ==
==Bibliografia==
* {{FOLDOC|complexity class|complexity class}}
*[http://qwiki.caltech.edu/wiki/Complexity_Zoo The Complexity Zoo]: una lista di classi di complessità, come riferimento per gli esperti.
*[http://www.cs.umass.edu/~immerman/complexity_theory.html Diagram] by [[Neil Immerman]] mostra la gerarchia delle classi di complessità e come queste si combinano tra di loro.
*[[Garey, Michael R.|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-Completo|NP-Completi]].
{{Classi di complessità}}
{{portale|informatica|matematica}}
{{Linguaggi formali e grammatiche}}
[[Categoria:Complessità computazionale]]
[[Categoria:Matematica per l'informatica]]
[[Categoria:Classi di complessità| ]]
[[de:Komplexitätsklasse]]
[[en:Complexity class]]
[[es:Clase de complejidad]]
[[fr:Classe de complexité]]
[[ko:복잡도 종류]]
[[nl:Complexiteitsgraad]]
[[pl:Klasa złożoności]]
[[ru:Класс сложности]]
| 