NL
#計算複雑性理論
#計算複雑性クラス
定義
$ \textbf{NL} \coloneqq \textbf{NSPACE}(\log n)
または
read-once certificate
を用いて
定義
$ L \in \textbf{NL}
であるとは、多項式
$ p
とlogspaceのTM
$ M
が存在してが存在して以下を満たすことである
$ x \in L \iff \exists_{u \in 2^{p(|x|)}} \left[M\{\text{\tt input:=} x, \text{\tt read-once:=} u\} = 1\right]
read-once tape
のヘッドの移動は停止
$ S
と右移動
$ R
のみ許可されたヘッドである
定理
NL完全問題
驚くべき定理：
Immerman-Szelepcsényiの定理
$ \textbf{coNL} = \textbf{NL}
関連
SPACE
L
coNL