查看“︁SC (複雜度)”︁的源代码

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

'''[[確定型上下文無關語言|DCFL]]'''，這個複雜度類是[[上下文無關語言]]的子集，使用[[確定下推自動機]]來驗證。DCFL已知是包含在'''SC'''內的，由Cook在1979年證明。<ref>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.</ref>

'''[[RL (複雜度)|RL]]'''和'''[[BPL (複雜度)|BPL]]'''是能夠以[[概率圖靈機]]在多項式時間和多項式對數空間解決的複雜度類。Nisan在1992年證明了一個較弱的[[去隨機化]]，因此可以證明這兩個複雜度類都在'''SC'''裡面。<ref>N. Nisan. RL is contained in SC, Proceedings of ACM STOC'92, pp. 619-623, 1992.</ref>換句話說，給出一個''多項式對數''空間，我們可以用一個確定型的圖靈機來模擬 ''對數''空間的機率演算法。

== 參考資料 ==
{{reflist}}


{{複雜度類}}

[[Category:複雜度類]]