- Limite
- Echivalenta
- ∀ functie g(n), Θ(g(n)) = { f(n) / ∃c1 >0, c1 >0 ai 0 ≦ c1g(n) ≦ f(n) ≦ c2G(n), ∀ n ≧ n0 } reprezinta multimea functiilor asimptotic echivalente cu g(n)
- Limita inferioara
- ∀ functie g(n), Ω(g(n)) = { f(n) / ∃c >0 ai 0 ≦ cg(n) ≦ f(n) , ∀ n ≧ n0 } reprezinta multimea functiilor marginite asimptotic inferior de g(n)
- Limita superioara
- ∀ functie g(n), O(g(n)) = { f(n) / ∃c >0 ai 0 ≦ f(n) ≦ cg(n) , ∀ n ≧ n0 } reprezinta multimea functiilor marginite asimptotic superior de g(n)
- Clase
- Limbaje
- P
- multimea limbajelor acceptate de o MTD in timp polinomial
Limbajul L ∈ P ⇔ ∃ M o MTD, ∃ Q(y), o functie polinomiala ai - v ∈ L ⇔ M accepta v
- M termina dupa cel mult Q(|v|) pasi
- NP
- multimea limbajelor acceptate de o MTN in timp polinomial
- co-NP
multimea limbajelor neacceptate de o MTN in timp polinomial
- PSPACE
- multimea limbajelor acceptate de o MTD in spatiu polinomial
- NPSPACE
- multimea limbajelor acceptate de o MTN in spatiu polinomial
- LOGSPACE
- multimea limbajelor acceptate de o MTD in spatiu logaritmic
- NLOGSPACE
- multimea limbajelor acceptate de o MTN in spatiu logaritmic
- EXP
- multimea limbajelor acceptate de o MTD in t(n)=2cn
- NEXP
- multimea limbajelor acceptate de o MTN in t(n)=2cn
- PEXP
- multimea limbajelor acceptate de o MTD in t(n)=2p(n)
- NPEXP
- multimea limbajelor acceptate de o MTN in t(n)=2p(n)
- UP
- multimea limbajelor acceptate de o MTN neambigua, care are cel putin o acceptare pentru orice intrare, in timp polinomial
- PP
- multimea limbajelor acceptate de o MTP (pseudo-aleatoare) in timp polinomial
- BPP (bounded error, probabilistic, polynomial time)
- multimea limbajelor acceptate de o MTP (echiprobabila) in timp polinomial
- RP
- multimea limbajelor acceptate de o MTP () in timp polinomial
- co-RP
- multimea limbajelor acceptate de MTP-RP la care probilitatiel de acceptare si neacceptare sunt inversate
- ZPP
- multimea limbajelor acceptate este intersectia RP si co-RP
- Functii
- PF
- Multimes functiilor calculate de o MTD in timp polinomial
- NPF
- Multimes functiilor calculate de o MTN in timp polinomial
- PSPACEF
- Multimes functiilor calculate de o MTD in spatiu polinomial
- #P
- Multimes functiilor care enumera calculele ale MTN-urilor
# posted by Sorin Badescu @ 2:57 PM