[[Categoria:Appendice]]


{|
|#P||Conta le soluzioni di un problema NP
|-
|#P-complete||I problemi più ardui in #P
|-
|[[AM]]||Problemi risolubili in tempi polinomiali da un protocollo di Arthur - Merlin
|-
|[[BPP]]||Problemi risolubili in tempi polinomiali da algoritmi randomizzati (la risposta è probabilmente corretta)
|-
|[[BQP]]||Problemi risolubili in tempi polinomiali da un [[computer]] [[quantistico]] (la risposta è probabilmente corretta)
|-
|[[Co-NP]]||Risposte NO verificabili in tempi polinomiali
|-
|[[Co-NP-complete]]||I problemi più ardui in Co-NP
|-
|[[DSPACE|DSPACE(f(''n''))]]||Risolubili da una macchina deterministica in spazio di memoria O(f(''n'')).
|-
|[[DTIME|DTIME(f(''n''))]]||Risolubili da una macchina deterministica in tempi O(f(''n'')).
|-
|[[E]]||Risolubili 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]]||Risolubili in spazi esponenziali
|-
|[[EXPTIME]]||Risolubili in tempi esponenziali
|-
|[[FNP]]||Analogo di NP per problemi di funzione
|-
|[[FP]]||Analogo di P per problemi di funzione
|-
|FP<sup>NP</sup>||Analogo di P<sup>NP</sup> per problemi di funzione; qui si colloca il problema del commesso viaggiatore
|-
|[[LOGSPACE]]||Sottoclasse dei problemi in P risolubili da un MT deterministica in spazio logaritmico
|-
|[[IP]]||Risolubili in tempi polinomiali da un sistema per dimostrazioni interattive
|-
|[[MA]]||Risolubili in tempi polinomiali da un protocollo Merlin - Arthur
|-
|[[NC]]||Risolubili efficientemente (in tempi polilogaritmici) con computer paralleli
|-
|[[NE]]||Risolubili da una macchina non-deterministica in tempi esponenziali con esponente lineare
|-
|[[NESPACE]]||Risolubili da una macchina non-deterministica in spazio esponenziale con esponente lineare
|-
|[[NEXP]]||Sinonimo di NEXPTIME
|-
|[[NEXPSPACE]]||Risolubili da una macchina non-deterministica in spazi esponenziali
|-
|[[NEXPTIME]]||Risolubili da una macchina non-deterministica in tempi esponenziali
|-
|[[NP]]||Risposte YES verificabili in tempi polinomiali
|-
|[[NP-Completo]]||I problemi più ardui in NP
|-
|[[NP-I]]||I problemi in NP non polinomiali ma non NP-C
|-
|[[NP-easy]]||Analogo a P<sup>NP</sup> per problemi di funzione; sinonimo di FP<sup>NP</sup>
|-
|[[NP-equivalent]]||I problemi più ardui in FP<sup>NP</sup>
|-
|[[NP-hard]]||O NP-complete o più arduo
|-
|[[NSPACE|NSPACE(f(''n''))]]||Risolubili da una macchina non-deterministica in uno spazio O(f(''n'')).
|-
|[[NTIME|NTIME(f(''n''))]]||Risolubili da una macchina non-deterministica in tempi O(f(''n'')).
|-
|[[P]]||Risolubili in tempi polinomiali
|-
|[[P-complete]]||I problemi più ardui risolubili in P da computer paralleli
|-
|[[PCP]]||Dimostrazioni verificabili probabilisticamente
|-
|[[PH]]||Unione delle classi della gerarchia polinomiale
|-
|P<sup>NP</sup>||Risolubili in tempi polinomiali da un [[oracolo]] per un problema in NP; sinonimo di Δ<sub>2</sub>P
|-
|[[PP]]||Probabilisticamente polinomiali (risposta corretta con probabilità leggermente superiore a 1/2)
|-
|[[PSPACE]]||Risolubili con memoria polinomiale in tempi illimitati
|-
|[[PSPACE-complete]]||I problemi più ardui in PSPACE
|-
|[[RP]]||Risolubili in tempi polinomiali da algoritmi randomizzati (la risposta NO è probabilmente corretta, la YES certamente corretta)
|-
|[[UP]]||Funzioni valutabili in tempi polinomiali non ambigui non-deterministici.
|-
|[[ZPP]]||Risolubili da algoritmi randomizzati (risposta sempre corretta, tempo medio di esecuzione polinomiale)
|}