Lista delle classi di complessità
(Reindirizzamento da Glossario delle classi di complessità)
Questa pagina contiene la lista delle classi di complessità, insiemi concernenti la teoria della complessità computazionale.
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 appartiene a NP, il complementare di 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 tempi 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 aritmetica |
| 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 | Complementare di 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 ritenuti 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 oppure 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, senza considerare il tempo |
| 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]
- ^ a b Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, 1ª ed., Cambridge University Press, 2009, ISBN 978-0-521-42426-4.
- ^ S2P: Second Level of the Symmetric Hierarchy, su qwiki.stanford.edu, Stanford University Complexity Zoo (archiviato dall'url originale il 14 ottobre 2012).
Collegamenti esterni[modifica | modifica wikitesto]
- Complexity Zoo - elenco di 467 classi di complessità, al gennaio 2008, e delle loro proprietà.
