SC (kompleksitet) - SC (complexity)
I beregningskompleksitetsteori er SC (Steve's Class, opkaldt efter Stephen Cook ) kompleksitetsklassen af problemer, der kan løses af en deterministisk Turing-maskine i polynomisk tid (klasse P ) og polylogaritmisk rum (klasse PolyL ) (det vil sige O ((log n) ) k ) plads til nogle konstante k ). Det kan også kaldes DTISP (poly, polylog) , hvor DTISP står for deterministisk tid og rum . Bemærk, at definitionen af SC adskiller sig fra P ∩ PolyL , da det for førstnævnte kræves, at en enkelt algoritme kører i både polynomisk tid og polylogaritmisk rum; mens for sidstnævnte er to separate algoritmer tilstrækkelige: en der kører i polynomisk tid, og en anden der kører i polylogaritmisk rum. (Det vides ikke, om SC og P ∩ PolyL er ækvivalente).
DCFL , den strenge delmængde af kontekstfrie sprog, der er anerkendt af deterministisk pushdown-automata , er indeholdt i SC , som vist af Cook i 1979.
Det er åbent, hvis rettet st-forbindelse er i SC , selvom det vides at være i P ∩ PolyL (på grund af en DFS-algoritme og Savitch's sætning ). Dette spørgsmål svarer til NL ⊆ SC .
RL og BPL er klasser af problemer, der kan accepteres af sandsynlige Turing-maskiner i logaritmisk rum og polynomisk tid. Noam Nisan viste i 1992 det svageresultat af derandomisering, at begge er indeholdt i SC . Med andre ord, givet polylogaritmisk rum, kan en deterministisk maskine simulere logaritmiske rumsandsynlige algoritmer.
