Seznam tříd složitosti - List of complexity classes
![]() | tento článek potřebuje další citace pro ověření.Duben 2010) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
Tohle je seznam třídy složitosti v teorie výpočetní složitosti. Další výpočetní a složité předměty viz seznam vyčíslitelnosti a složitosti témat.
Mnoho z těchto tříd má partnera „co“, který se skládá z: doplňuje všech jazyků v původní třídě. Například pokud je jazyk L v NP, pak doplněk L je v co-NP. (To neznamená, že doplňkem NP je co-NP - existují jazyky, o nichž je známo, že jsou v obou, a další jazyky, o nichž je známo, že nejsou ani v jednom.)
„Nejtěžší problémy“ třídy se vztahují k problémům, které ke třídě náležejí, takže každý další problém této třídy lze na ni omezit. Redukce je navíc problémem dané třídy nebo její podmnožiny.
#P | Počítejte řešení problému NP |
# P-kompletní | Nejtěžší problémy v #P |
2-EXPTIME | Řešitelné za dvojnásobně exponenciální čas |
AC0 | Třída složitosti obvodu ohraničené hloubky |
ACC0 | Třída složitosti obvodu ohraničené hloubky a počítání bran |
AC | Třída složitosti obvodu |
AH | Aritmetická hierarchie |
AP | Třída problémů střídavé Turingovy stroje umí řešit v polynomiálním čase.[1] |
APX | Problémy s optimalizací které mají aproximační algoritmy s konstantním aproximačním poměrem[1] |
DOPOLEDNE | Řešení v polynomiálním čase pomocí Protokol Arthur-Merlin[1] |
BPP | Řešení v polynomiálním čase o randomizované algoritmy (odpověď je pravděpodobně správná) |
BQP | Řešení v polynomiálním čase na a kvantový počítač (odpověď je pravděpodobně správná) |
co-NP | „NE“ odpovědi ověřitelné v polynomiálním čase nedeterministickým strojem |
co-NP-kompletní | Nejtěžší problémy v co-NP |
DSPACE (f (n)) | Řešitelné deterministickým strojem s prostorem O (f (n)). |
DTIME (f (n)) | Řešitelné deterministickým strojem v čase O (f (n)). |
E | Řešení v exponenciálním čase s lineárním exponentem |
ZÁKLADNÍ | Spojení tříd v exponenciální hierarchie |
ESPACE | Řešení s exponenciálním prostorem s lineárním exponentem |
EXP | Stejné jako EXPTIME |
EXPSPACE | Řešení s exponenciálním prostorem |
EXPTIME | Řešení v exponenciálním čase |
FNP | Analog NP pro funkční problémy |
FP | Analog P pro funkční problémy |
FPNP | Analog PNP pro funkční problémy; domov problém obchodního cestujícího |
FPT | Opravitelný parametr |
GapL | Logspace-redukovatelný na výpočet celočíselného determinantu matice |
IP | Řešení v polynomiálním čase pomocí interaktivní kontrolní systém |
L | Řešení logaritmickým (malým) prostorem |
LOGCFL | Logspace-redukovatelné na a bezkontextový jazyk |
MA | Řešení v polynomiálním čase a Protokol Merlin-Arthur |
NC | Efektivně řešitelné (v polylogaritmickém čase) na paralelních počítačích |
NE | Řešitelné nedeterministickým strojem v exponenciálním čase s lineárním exponentem |
NESPACE | Řešitelné nedeterministickým strojem s exponenciálním prostorem s lineárním exponentem |
NEXP | Stejné jako NEXPTIME |
NEXPSPACE | Řešitelné nedeterministickým strojem s exponenciálním prostorem |
NEXPTIME | Řešitelné nedeterministickým strojem v exponenciálním čase |
NL | Odpovědi „ANO“ lze ověřit pomocí logaritmického prostoru |
NELEMENTÁRNÍ | Doplněk ZÁKLADNÍ. |
NP | "ANO" odpovědi ověřitelné v polynomiálním čase (viz třídy složitosti P a NP ) |
NP-kompletní | Nejtěžší nebo nejexpresivnější problémy v NP |
NP-snadné | Analogicky k P.NP pro funkční problémy; jiný název pro FPNP |
NP-ekvivalent | Nejtěžší problémy v FPNP |
NP-tvrdé | Alespoň tak tvrdý jako každý problém v NP, ale není známo, že je ve stejné třídě složitosti |
NSPACE (f (n)) | Řešitelné nedeterministickým strojem s prostorem O (f (n)). |
NTIME (f (n)) | Řešitelné nedeterministickým strojem v čase O (f (n)). |
P | Řešení v polynomiálním čase |
P-kompletní | Nejtěžší problémy v P řešit na paralelních počítačích |
P / poly | Řešitelné v polynomiálním čase s „poradenským řetězcem“ v závislosti pouze na velikosti vstupu |
PCP | Pravděpodobně ověřitelný důkaz |
PH | Spojení tříd v EU polynomiální hierarchie |
PNP | Řešení v polynomiálním čase s věštec za problém v NP; také známý jako Δ2P |
PP | Pravděpodobistically Polynomial (odpověď je správná s pravděpodobností o něco více než ½) |
PPAD | Polynomiální paritní argumenty na řízených grafech |
PR | Řešitelné rekurzivním vytvářením aritmetických funkcí. |
PSPACE | Řešení s polynomiálním prostorem. |
PSPACE - kompletní | Nejtěžší problémy v systému PSPACE. |
PTAS | Schéma aproximace v polynomiálním čase (podtřída APX). |
R | Řešitelné v konečném čase. |
RE | Problémy, na které můžeme odpovědět „ANO“ v konečném čase, ale odpověď „NE“ nemusí přijít nikdy. |
RL | Řešení s logaritmickým prostorem pomocí náhodných algoritmů (ŽÁDNÁ odpověď je pravděpodobně správná, ANO je jistě správná) |
RP | Řešitelné v polynomiálním čase pomocí randomizovaných algoritmů (ŽÁDNÁ odpověď je pravděpodobně správná, ANO je jistě správná) |
SL | Problémy log-space redukovatelné na určení, zda existuje cesta mezi danými vrcholy v neorientovaném grafu. V říjnu 2004 bylo zjištěno, že tato třída je ve skutečnosti rovna L. |
S2P | hry jednoho kola se simultánními pohyby rozhodovanými deterministicky v polynomiálním čase[2] |
TFNP | Celkové funkční problémy řešitelné v nedeterministickém polynomiálním čase. Problém v této třídě má vlastnost, že každý input má výstup, jehož platnost lze efektivně kontrolovat, a výpočetní výzvou je najít platný výstup. |
NAHORU | Jednoznačné nedeterministické funkce Polytime. |
ZPL | Řešení pomocí randomizovaných algoritmů (odpověď je vždy správná, průměrné využití prostoru je logaritmické) |
ZPP | Řešitelné randomizovanými algoritmy (odpověď je vždy správná, průměrná doba běhu je polynomická) |
Reference
- ^ A b C Sanjeev Arora, Boaz Barak (2009), Výpočetní složitost: moderní přístup, Cambridge University Press; 1 vydání, ISBN 978-0-521-42426-4
- ^ „S2P: Druhá úroveň symetrické hierarchie “. Složitost Zoo Zoo Stanford. Archivovány od originál dne 14.10.2012. Citováno 2011-10-27.
externí odkazy
- Složitost Zoo - seznam více než 500 tříd složitosti a jejich vlastností