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-completo I problemi più difficili in #P
2-EXPTIME Risolvibili in temi doppiamente esponenziali
AC0 Una classe di complessità dei circuiti con profondità limitata
ACC0 Una classe di complessità dei circuiti con profondità limitata e porte contatrici
AC Una classe di complessità dei circuiti
AH La gerarchia arimetica
AP La classe dei problemi risolvibili da macchine di Turing alternanti in tempo polinomiale[1]
APX Problemi di ottimizzazione che hanno algoritmi di approssimazione con rapporto di approssimazione costante[1]
AM Problemi risolvibili in tempi polinomiali da un protocollo di Arthur-Merlin
BPP Problemi risolvibili in tempi polinomiali da algoritmi randomizzati (la risposta è probabilmente corretta)
BQP Problemi risolvibili in tempi polinomiali da un computer quantistico (la risposta è probabilmente corretta)
Co-NP Risposte "NO" verificabili in tempi polinomiali da una macchina non deterministica
Co-NP-completi I problemi più difficili in co-NP
DSPACE(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)).
E Risolvibili 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 Risolvibili in spazi esponenziali
EXPTIME Risolvibili 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
FPT Trattabili con parametri fissi
GapL Riducibili in spazio logaritmico alla computazione del determinate degli interi di una matrice
IP Risolvibili in tempi polinomiali da un sistema per dimostrazioni interattive
L Sottoclasse dei problemi in P risolvibili da una MT deterministica in spazio logaritmico
LOGCFL Riducibili in spazio logaritmico a un linguaggio libero dal contesto
MA Risolvibili in tempi polinomiali da un protocollo Merlin-Arthur
NC Risolvibili efficientemente (in tempi polilogaritmici) con computer paralleli
NE Risolvibili da una macchina non-deterministica in tempi esponenziali con esponente lineare
NESPACE Risolvibili da una macchina non deterministica in spazio esponenziale con esponente lineare
NEXP Sinonimo di NEXPTIME
NEXPSPACE Risolvibili da una macchina non-deterministica in spazi esponenziali
NEXPTIME Risolvibili da una macchina non-deterministica in tempi esponenziali
NL Risposte "YES" verificabili in spazi logaritmici
NONELEMENTARY Complemento of ELEMENTARY
NP Risposte "YES" verificabili in tempi polinomiali (vedi classi di complessità P e NP)
NP-completo I problemi più difficili in NP
NP-I I problemi in NP non polinomiali ma non NP-C
NP-facile Analogo a PNP per problemi di funzione; sinonimo di FPNP
NP-equivalente I problemi più difficili in FPNP
NP-difficile O NP-completo o più difficile
NSPACE(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)).
P Risolvibili in tempi polinomiali
P-completo I problemi più difficili risolvibili in P da computer paralleli
PCP Dimostrazioni verificabili probabilisticamente
PH Unione delle classi della gerarchia polinomiale
PNP Risolvibili in tempi polinomiali da un oracolo per un problema in NP; sinonimo di Δ2P
P/poly Risolvibili in tempo polinomiale data una "stringa di consigli" a seconda soltanto della dimensione degli input
PP Probabilisticamente polinomiali (risposta corretta con probabilità leggermente superiore a 1/2)
PR Risolvibili accumulando ricorsivamente le funzioni aritmetiche
PSPACE Risolvibili con memoria polinomiale in tempi illimitati
PSPACE-completo I problemi più difficili in PSPACE
R Risolvibili in una quantità di tempo finita
RE Problemi ai quali si può rispondere "YES" in una quantità di tempo finita, ma non potrebbe mai darsi una risposta a "NO"
RL Risolvibili in spazi logaritmici da algoritmi randomizzati (la risposta "NO" è probabilmente corretta, la "YES" certamente corretta)
RP Risolvibili in tempi polinomiali da algoritmi randomizzati (la risposta "NO" è probabilmente corretta, la "YES" certamente corretta)
SL Problemi 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 L
S2P Gioco fatto in circolo con mosse simultanee arbitrate deterministicamente in tempo polinomiale[2]
TFNP Problemi 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 valido
UP Funzioni valutabili in tempi polinomiali non ambigui non deterministici
ZPL Risolvibili da algoritmi randomizzati (la risposta è sempre corretta, lo spazio medio di esecuzione è logaritmico)
ZPP Risolvibili da algoritmi randomizzati (risposta sempre corretta, tempo medio di esecuzione polinomiale)

Note[modifica | modifica wikitesto]

  1. ^ a b Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, 1ª ed., Cambridge University Press, 2009, ISBN 978-0-521-42426-4.
  2. ^ S2P: Second Level of the Symmetric Hierarchy, Stanford University Complexity Zoo.

Collegamenti esterni[modifica | modifica wikitesto]

  • Complexity Zoo - elenco di 467 classi di complessità, al gennaio 2008, e delle loro proprietà.