Classe di complessità: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: Elimino interlinks |
m →Relazioni tra classi di complessità: wikilink |
||
| (12 versioni intermedie di 6 utenti non mostrate) | |||
Riga 1:
[[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 [[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à)|
Molte classi di complessità possono essere caratterizzate in termini della [[logica matematica]] necessaria ad esprimerle; vedi [[complessità descrittiva]].
Riga 9 ⟶ 10:
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) 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à.
Riga 17 ⟶ 18:
| 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 |
| [[
| colspan=2 |
| [[
|- align="center"
| colspan=3 |
Riga 32 ⟶ 33:
| colspan=4 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
| align="center" | [[
|}
|- align="center"
| colspan=3 | [[
|- align="center"
| colspan=3 |
Riga 42 ⟶ 43:
|}
|- align="center"
| colspan=3 | [[
|- align="center"
| colspan=3 |
Riga 49 ⟶ 50:
|}
|- align="center"
| colspan=3 | [[
|- align="center"
| colspan=3 |
Riga 56 ⟶ 57:
|}
|- align="center"
| colspan=3 | [[
|- align="center"
| colspan=8 |
Riga 63 ⟶ 64:
|}
|- align="center"
| [[
| width=40 | [[
| [[
| [[
|
| [[
|
| [[
|- align="center"
|
Riga 76 ⟶ 77:
| align="center" | [[Linguaggio dipendente dal contesto|Tipo 1 (dipendente dal contesto)]]
|}
| [[
| [[
| border="1" | [[
|
| [[
|
| colspan=1 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
| align="center" | [[PSPACE-
|}
|- align="center"
| [[
| [[
| [[
| [[
|
| [[
|- align="center"
| [[
| [[
|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
| align="center" | [[Co-NP]]
|}
| [[
|
| colspan=3 |
Riga 107 ⟶ 108:
|}
|- align="center"
| [[
| [[
| [[
| [[
|
| [[
|
| [[
|- align="center"
| [[
| [[
| [[
|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
Riga 126 ⟶ 127:
|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
| align="center" | [[BQP (complessità)|BQP]]
|}
| width=10 |
Riga 134 ⟶ 135:
|}
|- align="center"
| [[
| [[
| [[
| [[
|
| [[
|- align="center"
| [[
| [[
| colspan=6 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
Riga 148 ⟶ 149:
|}
|- align="center"
| [[
| [[
| [[
| colspan=4 |
| [[
|- align="center"
| [[
| colspan=2 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
Riga 165 ⟶ 166:
|}
|- align="center"
| [[
| colspan=2 | [[
|- align="center"
| colspan=3 |
Riga 173 ⟶ 174:
|}
|- align="center"
| colspan=3 | [[
|- align="center"
| colspan=3 |
Riga 181 ⟶ 182:
|}
==
* [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.▼
* [[Glossario delle classi di complessità]]▼
* [
* [[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.
== Voci correlate ==
* [[Teoria della calcolabilità]]
* [[Teoria della complessità computazionale]]
== Collegamenti esterni ==
* {{FOLDOC|complexity class|complexity class}}
▲*[http://qwiki.stanford.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}}
[[Categoria:
| |||