SC（複雑さ）

計算複雑性理論において、SC （スティーブン・クックにちなんで名付けられたスティーブのクラス）^{[ 1 ]}は、決定性チューリングマシンによって多項式時間（クラスP）および多重対数空間（クラスPolyL）（つまり、ある定数kに対してO ((log n ) ^k ) 空間）で解ける問題の複雑性クラスである。これはDTISP(poly, polylog)と呼ばれることもあり、DTISP は決定性時間および空間を表す。 SCの定義はP ∩ PolyLとは異なり、前者では単一のアルゴリズムが多項式時間と多重対数空間の両方で実行する必要があるのに対し、後者では、多項式時間で実行されるアルゴリズムと多重対数空間で実行されるアルゴリズムの 2 つで十分である。SCとP ∩ PolyLが同等であるかどうかは不明である。

決定性プッシュダウンオートマトンによって認識される文脈自由言語の厳密な部分集合であるDCFL は、 SCに含まれることが 1979 年に Cook によって示されました。 ^{[ 2 ]}すべての文脈自由言語がP ∩ PolyLに含まれることが知られていますが、 SCで認識できるかどうかは未解決です。 ^{[ 3 ]}

有向st-連結性がSCに含まれるかどうかは未解決であるが、 P ∩ PolyLに含まれることは知られている。深さ優先探索は多項式時間で解くことができ、サビッチの定理は空間 上で解を与える。この問題はNL ⊆ SCと同値である。^{[ 4 ]}${\displaystyle O(\log^{2}n)}$

RLとBPLは、対数空間と多項式時間において確率的チューリングマシンが許容可能な問題のクラスである。Noam Nisanは1992年に、弱いデランダム化の結果から、両者がSCに含まれること。 ^{[ 5 ]}言い換えれば、多項式空間が与えられれば、決定論的マシンは対数空間確率アルゴリズムをシミュレートできる。

参考文献

1. 複雑性動物園: SC
2. SA Cook. 決定論的CFLは多項式時間と対数二乗空間で同時に受け入れられる. ACM STOC'79 Proceedings, pp. 338–345. 1979.
3. TCS Stack Exchange: o(n^2) 空間を使用した CFG 解析
4. Chakraborty, Diptarka; Tewari, Raghunath (2018). 「有向階層化平面グラフにおける到達可能性のための空間および多項式時間アルゴリズム」ACM Transactions on Computation Theory . 9 (4): 19:1–19:11. arXiv : 1501.05828 . doi : 10.1145/3154857 .${\displaystyle O(n^{\varepsilon })}$
5. Nisan, Noam (1992)、「RL ⊆ SC」、第24回ACMコンピューティング理論シンポジウム（STOC '92）の議事録、ビクトリア、ブリティッシュコロンビア州、カナダ、pp.  619– 623、doi : 10.1145/129712.129772、S2CID 11651375 。