SC (složitost) - SC (complexity)
v teorie výpočetní složitosti, SC (Steveova třída, pojmenovaná po Stephen Cook )[1] je třída složitosti problémů řešitelných a deterministický Turingův stroj v polynomiálním čase (třída P) a polylogaritmický prostor (třída PolyL) (to znamená, Ó ((log n)k) prostor pro nějakou konstantu k). Může se také nazývat DTISP (poly, polylog), kde DTISP znamená deterministický čas a prostor. Všimněte si, že definice SC se liší od P ∩ PolyL, protože pro první je nutné, aby jeden algoritmus běžel jak v polynomiálním čase, tak v polylogaritmickém prostoru; zatímco pro druhé budou stačit dva samostatné algoritmy: jeden běžící v polynomiálním čase a druhý běžící v polylogaritmickém prostoru. (Není známo, zda SC a P ∩ PolyL jsou ekvivalentní).
DCFL, přísná podmnožina bezkontextové jazyky uznán deterministické posunovací automaty, je obsažen v SC, jak ukazuje Cook v roce 1979.[2]
Je otevřený, pokud je nasměrován st-konektivita je v SC, i když je známo, že je v P ∩ PolyL (kvůli algoritmu DFS a Savitchova věta ). Tato otázka je ekvivalentní k NL ⊆ SC.
RL a BPL jsou třídy problémů přijatelné pro pravděpodobnostní Turingovy stroje v logaritmickém prostoru a polynomiálním čase. Noam Nisan v roce 1992 ukázal slabé derandomizace výsledek, že oba jsou obsaženy v SC.[3] Jinými slovy řečeno polylogaritmický prostor, může deterministický stroj simulovat logaritmický prostorové pravděpodobnostní algoritmy.
Reference
- ^ Složitost Zoo: SC
- ^ S. A. Cook. Deterministické CFL jsou přijímány současně v polynomiálním čase a logu na druhou. Sborník ACM STOC'79, s. 338–345. 1979.
- ^ Nisan, Noame (1992), „RL ⊆ SC“, Sborník 24. sympozia ACM o teorii práce s počítačem (STOC '92), Victoria, Britská Kolumbie, Kanada, str. 619–623, doi:10.1145/129712.129772.
P ≟ NP | Tento teoretická informatika –Vztahující se článek je pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |