Glossario delle classi di complessità

Da Wikipedia, l'enciclopedia libera.

Questa pagina presenta un glossario delle classi di complessità, insiemi concernenti la teoria della complessità computazionale. Per altre pagine su argomenti computazionali e di complessità vedi elenco degli articoli di computabilità e complessità.

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 L appartiene a NP, il complementare di 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-complete	I problemi più duri 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ù duri 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
FP^NP	Analogo di P^NP 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 (vedi classi di complessità P e NP)
NP-Completi	I problemi più duri in NP
NP-I	I problemi in NP non polinomiali ma non NP-C
NP-easy	Analogo a P^NP per problemi di funzione; sinonimo di FP^NP
NP-equivalent	I problemi più duri in FP^NP
NP-hard	O NP-complete o più duro
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ù duri risolubili in P da computer paralleli
PCP	Dimostrazioni verificabili probabilisticamente
PH	Unione delle classi della gerarchia polinomiale
P^NP	Risolubili in tempi polinomiali da un oracolo per un problema in NP; sinonimo di Δ₂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ù duri 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)

[modifica] Collegamenti esterni

Complexity Zoo - elenco di 467 classi di complessità, al gennaio 2008, e delle loro proprietà
Complexlab - Un ambito di conversazione sui temi della complessità applicata al management delle organizzazioni.

Classi di complessità (elenco)
P • NP • co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • EXPSPACE • PR • RE • Co-RE • RE-C • Co-RE-C • R • BQP • BPP • RP • ZPP • PCP • IP • PH