SPACE
#計算複雑性理論
#計算複雑性クラス
$ S : \mathbb{N} \to \mathbb{N}
, 言語
$ L \subseteq 2^*
について,
$ L
が
$ \textbf{SPACE}(S)
であるとは、定数
$ c
が存在して大きさ
$ cS(n)
のspace-bounded turing machineが存在して
$ L
を決定することである
関連
NSPACE