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 appartiene a NP, il complementare di 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.
#PConta le soluzioni di un problema NP#P-completoI problemi più difficili in #P2-EXPTIMERisolvibili in tempi doppiamente esponenziali AC0Una classe di complessità dei circuiti con profondità limitataACC0Una classe di complessità dei circuiti con profondità limitata e porte contatriciACUna classe di complessità dei circuiti AHLa gerarchia aritmeticaAPLa classe dei problemi risolvibili da macchine di Turing alternanti in tempo polinomialeAPXProblemi di ottimizzazione che hanno algoritmi di approssimazione con rapporto di approssimazione costanteAMProblemi risolvibili in tempi polinomiali da un protocollo di Arthur-MerlinBPPProblemi risolvibili in tempi polinomiali da algoritmi randomizzati (la risposta è probabilmente corretta)BQPProblemi risolvibili in tempi polinomiali da un computer quantistico (la risposta è probabilmente corretta)Co-NPRisposte "NO" verificabili in tempi polinomiali da una macchina non deterministicaCo-NP-completiI problemi più difficili in co-NPDSPACE(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)).ERisolvibili in tempi esponenziali con esponenti lineari nel tempoELEMENTARYUnione delle classi nella gerarchia esponenzialeESPACERisolubili in spazi esponenziali con esponente lineare nello spazioEXPSinonimo di EXPTIMEEXPSPACERisolvibili in spazi esponenzialiEXPTIMERisolvibili in tempi esponenzialiFNPAnalogo di NP per problemi di funzioneFPAnalogo di P per problemi di funzioneFPNPAnalogo di PNP per problemi di funzione; qui si colloca il problema del commesso viaggiatoreFPTTrattabili con parametri fissiGapLRiducibili in spazio logaritmico alla computazione del determinate degli interi di una matriceIPRisolvibili in tempi polinomiali da un sistema per dimostrazioni interattiveLSottoclasse dei problemi in P risolvibili da una MT deterministica in spazio logaritmicoLOGCFLRiducibili in spazio logaritmico a un linguaggio libero dal contestoMARisolvibili in tempi polinomiali da un protocollo Merlin-ArthurNCRisolvibili efficientemente (in tempi polilogaritmici) con computer paralleliNERisolvibili da una macchina non-deterministica in tempi esponenziali con esponente lineareNESPACERisolvibili da una macchina non deterministica in spazio esponenziale con esponente lineareNEXPSinonimo di NEXPTIMENEXPSPACERisolvibili da una macchina non-deterministica in spazi esponenzialiNEXPTIMERisolvibili da una macchina non-deterministica in tempi esponenzialiNLRisposte "YES" verificabili in spazi logaritmiciNONELEMENTARYComplementare di ELEMENTARYNPRisposte "YES" verificabili in tempi polinomiali (vedi classi di complessità P e NP)NP-completoI problemi più difficili in NPNP-II problemi in NP ritenuti non polinomiali ma non NP-CNP-facileAnalogo a PNP per problemi di funzione; sinonimo di FPNPNP-equivalenteI problemi più difficili in FPNPNP-difficileO NP-completo oppure più difficileNSPACE(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)).PRisolvibili in tempi polinomialiP-completoI problemi più difficili risolvibili in P da computer paralleliPCPDimostrazioni verificabili probabilisticamentePHUnione delle classi della gerarchia polinomialePNPRisolvibili in tempi polinomiali da un oracolo per un problema in NP; sinonimo di Δ2PP/polyRisolvibili in tempo polinomiale data una "stringa di consigli" a seconda soltanto della dimensione degli inputPPProbabilisticamente polinomiali (risposta corretta con probabilità leggermente superiore a 1/2)PRRisolvibili accumulando ricorsivamente le funzioni aritmetichePSPACERisolvibili con memoria polinomiale, senza considerare il tempoPSPACE-completoI problemi più difficili in PSPACERRisolvibili in una quantità di tempo finitaREProblemi ai quali si può rispondere "YES" in una quantità di tempo finita, ma non potrebbe mai darsi una risposta a "NO"RLRisolvibili in spazi logaritmici da algoritmi randomizzati (la risposta "NO" è probabilmente corretta, la "YES" certamente corretta)RPRisolvibili in tempi polinomiali da algoritmi randomizzati (la risposta "NO" è probabilmente corretta, la "YES" certamente corretta)SLProblemi 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 LS2PGioco fatto in circolo con mosse simultanee arbitrate deterministicamente in tempo polinomialeTFNPProblemi 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 validoUPFunzioni valutabili in tempi polinomiali non ambigui non deterministiciZPLRisolvibili da algoritmi randomizzati (la risposta è sempre corretta, lo spazio medio di esecuzione è logaritmico)ZPPRisolvibili da algoritmi randomizzati (risposta sempre corretta, tempo medio di esecuzione polinomiale)
Note
Collegamenti esterni Complexity Zoo - elenco di 467 classi di complessità, al gennaio 2008, e delle loro proprietà.
* Classi di complessità Classi di complessità