Appendice:Classi di complessità

Da Wikizionario, il dizionario a contenuto aperto.
Jump to navigation Jump to search


#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)