SC (複雜度)

在計算複雜度理論內，SC (Steve's Class，以史蒂芬·庫克命名)^[1]是一個複雜度類，包含了使用圖靈機，在多項式時間(P複雜度類)以及多項式對數空間(PolyL複雜度類) (也就是，O(log^k n)空間，k是某個常數)。我們也可以稱呼這個複雜度類為DTISP(poly, polylog)，這裏DTISP代表確定性時間與空間(deterministic time and space)。這裏的SC是P ${\displaystyle \cap }$ PolyL的嚴格子集，因為對前者，他需要存在一個解決問題的演算法同時滿足多項式時間以及多項式對數空間兩個條件；而對後者這個聯集來說，他只需要兩個各自的演算法，其中一個是多項式時間，另一個是多項式對數空間即可以滿足。

DCFL，這個複雜度類是上下文無關語言的子集，使用確定下推自動機來驗證。DCFL已知是包含在SC內的，由Cook在1979年證明。^[2]

RL和BPL是能夠以概率圖靈機在多項式時間和多項式對數空間解決的複雜度類。Nisan在1992年證明了一個較弱的去隨機化，因此可以證明這兩個複雜度類都在SC裏面。^[3]換句話說，給出一個多項式對數空間，我們可以用一個確定型的圖靈機來模擬 對數空間的概率演算法。

參考資料

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.