SC (复杂度)

在计算复杂度理论内，SC (Steve's Class，以史蒂芬·库克命名)^[1]是一个复杂度类，包含了使用图灵机，在多项式时间(P复杂度类)以及多项式对数空间(PolyL复杂度类) (也就是，O(log^k n)空间，k是某个常数)。我们也可以称呼这个复杂度类为DTISP(poly, polylog)，这里DTISP代表确定性时间与空间(deterministic time and space)。这里的SC是P $\cap$ PolyL的严格子集，因为对前者，他需要存在一个解决问题的算法同时满足多项式时间以及多项式对数空间两个条件；而对后者这个联集来说，他只需要两个各自的算法，其中一个是多项式时间，另一个是多项式对数空间即可以满足。

DCFL，这个复杂度类是上下文无关语言的子集，使用确定下推自动机来验证。DCFL已知是包含在SC内的，由Cook在1979年证明。^[2]

RL和BPL是能够以概率图灵机在多项式时间和多项式对数空间解决的复杂度类。Nisan在1992年证明了一个较弱的去随机化，因此可以证明这两个复杂度类都在SC里面。^[3]换句话说，给出一个多项式对数空间，我们可以用一个确定型的图灵机来模拟对数空间的几率算法。

参考资料[编辑]

^ Complexity Zoo: SC
^ S. A. Cook. Deterministic CFL's are accepted simultaneously in polynomial time and log squared space. Proceedings of ACM STOC'79, pp. 338–345. 1979.
^ N. Nisan. RL is contained in SC, Proceedings of ACM STOC'92, pp. 619-623, 1992.

[1] Complexity Zoo: SC

[2] S. A. Cook. Deterministic CFL's are accepted simultaneously in polynomial time and log squared space. Proceedings of ACM STOC'79, pp. 338–345. 1979.

[3] N. Nisan. RL is contained in SC, Proceedings of ACM STOC'92, pp. 619-623, 1992.

[1]

[2]

[3]