Appendice:Classi di complessità
| #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(f(n)) | Risolubili da una macchina deterministica in spazio di memoria O(f(n)). |
| 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 |
| FPNP | Analogo di PNP 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 PNP per problemi di funzione; sinonimo di FPNP |
| NP-equivalent | I problemi più ardui in FPNP |
| NP-hard | O NP-complete o più arduo |
| NSPACE(f(n)) | Risolubili da una macchina non-deterministica in uno spazio O(f(n)). |
| 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 |
| PNP | Risolubili in tempi polinomiali da un oracolo per un problema in NP; sinonimo di Δ2P |
| 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) |