Classe di complessità: differenze tra le versioni

Versione delle 18:22, 23 set 2016

Versione attuale delle 21:35, 15 feb 2025

(6 versioni intermedie di 3 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

Riga 84 ⟶ 85:

| colspan=1 |

{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"

| align="center" | [[PSPACE-Completocompleto|PSPACE-Completi]]

|}

|- align="center"

Riga 126 ⟶ 127:

|

{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"

| align="center" | [[BQP (complessità)|BQP]]

|}

| width=10 |

Riga 182 ⟶ 183:

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

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

* {{FOLDOC|complexity class|complexity class}}

{{Classi di complessità}}