Wikipedia

Classe di complessità: differenze tra le versioni

Naviga nella cronologia in modo interattivo
← Differenza precedente
Contenuto cancellato Contenuto aggiunto
VisualeWikitesto
 
(22 versioni intermedie di 13 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à)|'''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 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 (complessità)|'''FP''']].
 
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, 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"
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 |
| [[ImmagineFile:solidLine.png]]
| colspan=2 |
| [[ImmagineFile:solidLine.png]]
|- align="center"
| colspan=3 |
Riga 32 ⟶ 33:
| colspan=4 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
| align="center" | [[ProblemiProblema di decisionedecisionale|Indecidibili]]
|}
|- align="center"
| colspan=3 | [[ImmagineFile:solidLine.png]]
|- align="center"
| colspan=3 |
Riga 42 ⟶ 43:
|}
|- align="center"
| colspan=3 | [[ImmagineFile:solidLine.png]]
|- align="center"
| colspan=3 |
Riga 49 ⟶ 50:
|}
|- align="center"
| colspan=3 | [[ImmagineFile:dottedLine.png]]
|- align="center"
| colspan=3 |
Riga 56 ⟶ 57:
|}
|- align="center"
| colspan=3 | [[ImmagineFile:dottedLine.png]]
|- align="center"
| colspan=8 |
Riga 63 ⟶ 64:
|}
|- align="center"
| [[ImmagineFile:solidLine.png]]
| width=40 | [[ImmagineFile:solidLine.png]]
| [[ImmagineFile:dottedLine.png]]
| [[ImmagineFile:dottedLine.png]]
|
| [[ImmagineFile:dottedLine.png]]
|
| [[ImmagineFile:dottedLine.png]]
|- align="center"
|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
| align="center" | [[GrammaticaLinguaggio sensibiledipendente aldal contesto|Tipo 1 (sensibiledipendente aldal contesto)]]
|}
| [[ImmagineFile:solidLine.png]]
| [[ImmagineFile:dottedLine.png]]
| border="1" | [[ImmagineFile:dottedLine.png]]
|
| [[ImmagineFile:dottedLine.png]]
|
| colspan=1 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
| align="center" | [[PSPACE-Completocompleto|PSPACE-Completi]]
|}
|- align="center"
| [[ImmagineFile:solidLine.png]]
| [[ImmagineFile:solidLine.png]]
| [[ImmagineFile:dottedLine.png]]
| [[ImmagineFile:dottedLine.png]]
|
| [[ImmagineFile:dottedLine.png]]
|- align="center"
| [[ImmagineFile:solidLine.png]]
| [[ImmagineFile:solidLine.png]]
|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
| align="center" | [[Co-NP]]
|}
| [[ImmagineFile:dottedLine.png]]
|
| colspan=3 |
Riga 107 ⟶ 108:
|}
|- align="center"
| [[ImmagineFile:solidLine.png]]
| [[ImmagineFile:solidLine.png]]
| [[ImmagineFile:dottedLine.png]]
| [[ImmagineFile:dottedLine.png]]
|
| [[ImmagineFile:dottedLine.png]]
|
| [[ImmagineFile:dottedLine.png]]
|- align="center"
| [[ImmagineFile:solidLine.png]]
| [[ImmagineFile:solidLine.png]]
| [[ImmagineFile:dottedLine.png]]
|
{| 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"
| [[ImmagineFile:solidLine.png]]
| [[ImmagineFile:solidLine.png]]
| [[ImmagineFile:dottedLine.png]]
| [[ImmagineFile:dottedLine.png]]
|
| [[ImmagineFile:dottedLine.png]]
|- align="center"
| [[ImmagineFile:solidLine.png]]
| [[ImmagineFile:solidLine.png]]
| colspan=6 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
Riga 148 ⟶ 149:
|}
|- align="center"
| [[ImmagineFile:solidLine.png]]
| [[ImmagineFile:solidLine.png]]
| [[ImmagineFile:dottedLine.png]]
| colspan=4 |
| [[ImmagineFile:dottedLine.png]]
|- align="center"
| [[ImmagineFile:solidLine.png]]
| colspan=2 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
Riga 165 ⟶ 166:
|}
|- align="center"
| [[ImmagineFile:solidLine.png]]
| colspan=2 | [[ImmagineFile:solidLine.png]]
|- align="center"
| colspan=3 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
| align="center" | [[GrammaticaLinguaggio liberalibero dal contesto|Tipo 2 (liberalibero dal contesto)]]
|}
|- align="center"
| colspan=3 | [[ImmagineFile:solidLine.png]]
|- align="center"
| colspan=3 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
| align="center" | [[GrammaticaLinguaggio regolare|Tipo 3 (Regolare)]]
|}
|}
 
==Voci correlateBibliografia ==
* [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à]]▼
* [httphttps://wwwweb.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 ==
▲* [[GlossarioLista delle classi di complessità]]
* [[Teoria della calcolabilità]]
* [[Teoria della complessità computazionale]]
 
== Collegamenti esterni ==
==Bibliografia==
* {{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}}
{{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]]
[[fa:کلاس پیچیدگی]]
[[fr:Classe de complexité]]
[[hr:Klasa složenosti]]
[[ja:複雑性クラス]]
[[ko:복잡도 종류]]
[[nl:Complexiteitsgraad]]
[[pl:Klasa złożoności]]
[[ru:Класс сложности]]
[[uk:Обчислювальна складність]]
Estratto da "https://it.wikipedia.org/wiki/Classe_di_complessità"