Lista delle classi di complessità

Questa pagina contiene la lista delle classi di complessità, insiemi concernenti la teoria della complessità computazionale.

Nell'articolo computazione compare una mappa delle relazioni di inclusione dimostrabili per le classi di complessità. Molte delle classi sottoindicate hanno una classe associata in modo involutorio che chiamiamo "co-duale" costituita dai complementi di tutti i linguaggi della classe originale. Ad esempio, se il linguaggio ${\displaystyle {\mathcal {L}}}$ appartiene a NP, il complementare di ${\displaystyle {\mathcal {L}}}$ sta in co-NP (questo non è il complementare dell'insieme di linguaggi NP, in quanto vi sono linguaggi in entrambe queste classi e linguaggi che non appartengono a nessuno dei due). Per una classe co-duale non presente in genere è utile esaminare la associata: ad esempio da UP si possono ricavare indicazioni per co-UP.

#P	Conta le soluzioni di un problema NP
#P-completo	I problemi più difficili in #P
2-EXPTIME	Risolvibili in tempi doppiamente esponenziali
AC0	Una classe di complessità dei circuiti con profondità limitata
ACC0	Una classe di complessità dei circuiti con profondità limitata e porte contatrici
AC	Una classe di complessità dei circuiti
AH	La gerarchia aritmetica
AP	La classe dei problemi risolvibili da macchine di Turing alternanti in tempo polinomiale[1]
APX	Problemi di ottimizzazione che hanno algoritmi di approssimazione con rapporto di approssimazione costante[1]
AM	Problemi risolvibili in tempi polinomiali da un protocollo di Arthur-Merlin
BPP	Problemi risolvibili in tempi polinomiali da algoritmi randomizzati (la risposta è probabilmente corretta)
BQP	Problemi risolvibili in tempi polinomiali da un computer quantistico (la risposta è probabilmente corretta)
Co-NP	Risposte "NO" verificabili in tempi polinomiali da una macchina non deterministica
Co-NP-completi	I problemi più difficili in co-NP
DSPACE(f(n))	Risolvibili da una macchina deterministica in spazio di memoria O(f(n)).
DTIME(f(n))	Risolvibili da una macchina deterministica in tempi O(f(n)).
E	Risolvibili in tempi esponenziali con esponenti lineari nel tempo
ELEMENTARY	Unione delle classi nella gerarchia esponenziale
ESPACE	Risolubili in spazi esponenziali con esponente lineare nello spazio
EXP	Sinonimo di EXPTIME
EXPSPACE	Risolvibili in spazi esponenziali
EXPTIME	Risolvibili in tempi esponenziali
FNP	Analogo di NP per problemi di funzione
FP	Analogo di P per problemi di funzione
FP^NP	Analogo di P^NP per problemi di funzione; qui si colloca il problema del commesso viaggiatore
FPT	Trattabili con parametri fissi
GapL	Riducibili in spazio logaritmico alla computazione del determinate degli interi di una matrice
IP	Risolvibili in tempi polinomiali da un sistema per dimostrazioni interattive
L	Sottoclasse dei problemi in P risolvibili da una MT deterministica in spazio logaritmico
LOGCFL	Riducibili in spazio logaritmico a un linguaggio libero dal contesto
MA	Risolvibili in tempi polinomiali da un protocollo Merlin-Arthur
NC	Risolvibili efficientemente (in tempi polilogaritmici) con computer paralleli
NE	Risolvibili da una macchina non-deterministica in tempi esponenziali con esponente lineare
NESPACE	Risolvibili da una macchina non deterministica in spazio esponenziale con esponente lineare
NEXP	Sinonimo di NEXPTIME
NEXPSPACE	Risolvibili da una macchina non-deterministica in spazi esponenziali
NEXPTIME	Risolvibili da una macchina non-deterministica in tempi esponenziali
NL	Risposte "YES" verificabili in spazi logaritmici
NONELEMENTARY	Complementare di ELEMENTARY
NP	Risposte "YES" verificabili in tempi polinomiali (vedi classi di complessità P e NP)
NP-completo	I problemi più difficili in NP
NP-I	I problemi in NP ritenuti non polinomiali ma non NP-C
NP-facile	Analogo a P^NP per problemi di funzione; sinonimo di FP^NP
NP-equivalente	I problemi più difficili in FP^NP
NP-difficile	O NP-completo oppure più difficile
NSPACE(f(n))	Risolvibili da una macchina non deterministica in uno spazio O(f(n)).
NTIME(f(n))	Risolvibili da una macchina non deterministica in tempi O(f(n)).
P	Risolvibili in tempi polinomiali
P-completo	I problemi più difficili risolvibili in P da computer paralleli
PCP	Dimostrazioni verificabili probabilisticamente
PH	Unione delle classi della gerarchia polinomiale
P^NP	Risolvibili in tempi polinomiali da un oracolo per un problema in NP; sinonimo di Δ2P
P/poly	Risolvibili in tempo polinomiale data una "stringa di consigli" a seconda soltanto della dimensione degli input
PP	Probabilisticamente polinomiali (risposta corretta con probabilità leggermente superiore a 1/2)
PR	Risolvibili accumulando ricorsivamente le funzioni aritmetiche
PSPACE	Risolvibili con memoria polinomiale, senza considerare il tempo
PSPACE-completo	I problemi più difficili in PSPACE
R	Risolvibili in una quantità di tempo finita
RE	Problemi ai quali si può rispondere "YES" in una quantità di tempo finita, ma non potrebbe mai darsi una risposta a "NO"
RL	Risolvibili in spazi logaritmici da algoritmi randomizzati (la risposta "NO" è probabilmente corretta, la "YES" certamente corretta)
RP	Risolvibili in tempi polinomiali da algoritmi randomizzati (la risposta "NO" è probabilmente corretta, la "YES" certamente corretta)
SL	Problemi riducibili in spazi logaritmici a determinare se esiste un cammino tra i vertici dati di un grafo indiretto. Nell'ottobre 2004 si è scoperto che questa classe è in realtà uguale a L
S2P	Gioco fatto in circolo con mosse simultanee arbitrate deterministicamente in tempo polinomiale[2]
TFNP	Problemi di funzione totali risolvibili in tempi polinomiali non deterministici. Un problema in questa classe ha la proprietà che ogni input ha un output la cui validità può essere verificata in modo efficiente, e la sfida computazionale è trovare un output valido
UP	Funzioni valutabili in tempi polinomiali non ambigui non deterministici
ZPL	Risolvibili da algoritmi randomizzati (la risposta è sempre corretta, lo spazio medio di esecuzione è logaritmico)
ZPP	Risolvibili da algoritmi randomizzati (risposta sempre corretta, tempo medio di esecuzione polinomiale)

Note

1. Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, 1ª ed., Cambridge University Press, 2009, ISBN 978-0-521-42426-4.
2. S₂P: Second Level of the Symmetric Hierarchy, su qwiki.stanford.edu, Stanford University Complexity Zoo (archiviato dall'url originale il 14 ottobre 2012).

Collegamenti esterni

• Complexity Zoo - elenco di 467 classi di complessità, al gennaio 2008, e delle loro proprietà.