数理解析研究所講究録
第 1849 巻 2013 年 37-4437対数空間階層の相対化
太田浩行 (Hiroyuki Ota)

河村彰星 (Akitoshi Kawamura)

東京大学 (University of Tokyo)

1 導入
神託

$\alpha$$C$ を計算するモデルに神託に対する計算量クラス $C$ の相対化とは，に計算可能な言語の集合である．神託$C(\alpha)$$\alpha$に対する計算量クラス

は $C$ の計算モデルに依存するため，クラス $C$ と言語$C$の相対化を$\alpha$を付け足した時$C(\alpha)$と表記する 1.
$*$から自明に定義されるものではない．

$\alpha$

対数領域計算量クラス $L,$ $NL$ と回路計算量クラス $NC^{i},$ $AC^{i}$ は$NC^{1}\subseteq L\subseteq NL\prime\subseteq AC^{1}$の包含関係を満たす．一方で自明な相対化は，$NC^{1}(\alpha)\subseteq L(\alpha)\subseteq NL(\alpha)\subseteq AC^{1}(\alpha)$(1)を満たさないことが知られており，これらのクラスの相対化の様々な定義が提案されてきた[1, 2, 4, 8].
$NC^{i},$ $L,$ $NL$Aehlig, Cook, Nguyen は (1) の関係を満たすの相対化を初めて定義した[1]. さらにそれら相対化は $AC$ O 還元につぃて良い性質をもっており，非相対化クラスの $AC$ O 完$AC^{i},$全問題が，相対化クラスの$AC^{0}(\alpha)$

完全問題となってぃる．つまり$NC^{1}(\alpha)=AC^{0}($FORMVAL,$L(\alpha)=AC^{0}(1-$$NL(\alpha)\subseteq AC^{0}($STCONN,STCONN,$\alpha)$,$\alpha)$,$\alpha)$(2).

ただし $NC^{1}$ 完全問題 FORMVAL は変数のない命題論理式の評価，$L$
完全問題 1-STCONN は出次数が 1 以下に制限された有向グラフでの到達可能性問題，$NL$ 完全問題 STCONN は有向グラフでの到達可能性問題である．
式 (2) において $NL(\alpha)$ のみ等号関係が成り立つか否かがわかっておらず，彼らは $NL$ ’ $(\alpha)=$$AC^{0}($STCONN,$\alpha)$を満たすような $NL$ の相対化 $NL$ ’いる．

$*1C^{\alpha}$と書かれることもある．

$(\alpha)$を定義することを課題として述べて

38$NL$ は自らを第一層として定義されところで Immerman-Szelepcsenyi の定理 [3, 7] により，る階層全体 NLH に等しい．そこで本稿では L や $NL$ の代りにそこから定義される階層 $LH$ やNLH について考える．これらを適切に相対化したものが$LH(\alpha)=AC^{0}(1-$STCONN,NLH $(\alpha)=AC^{0}($ STCONN,$\alpha)$,$\alpha)$

及び$NC^{1}(\alpha)\subseteq LH(\alpha)\subseteq$NLH$(\alpha)\subseteq AC^{1}(\alpha)$を満たすことを示す．
なお $AC^{0}$ は補集合を取る操作について閉じているため，Aehlig, Cook, Nguyen の要請する’$NL$ $(\alpha)=AC^{0}($STCONN,$\alpha)$’$NL$が満たされるには，$(\alpha)$

もまた補集合について閉じている，即$NL$ そのものを
ち Immerman-Szelepcs\’enyi の定理 [3, 7] が相対化された形で成立つ必要がある．

このように相対化できるかはまだ不明である．

2回路計算量の相対化
回路計算量クラス $NC^{i},$ $AC^{i},$ $AC^{0}(m),$ $TC^{0}$ の相対化を Aehlig 等の定義 [1] と同様に定義する．一様性としては DLOGTIME を採用する．

(resp. $AC^{i}(m)$ ,とは，神託ゲートを含む回路によって計算される言語のクラスである．とは，2 入力 AND, 2 入力 $OR,$, 神託ゲートのネストの深さが $O(\log^{i-1}(n))$
NOT, 神託ゲートから構成され，深さが定義 1.

$AC^{i}(\alpha)$$(resp. AC^{i}(m, \alpha),$$AC^{i}$$TC^{0}(\alpha))$$NC^{i}(\alpha)$$TC^{0})$$O(\log^{i}(n))$

である回路族によって計算される言語のクラスである．
ただし神託ゲート$\alpha$とは，入力$x$にたいして $x\in\alpha$ ならば 1 を，そうでなければ$0$を出力するゲートとする．

このように定義されたクラスは非相対化クラスと同様の包含関係を満たす．
$AC^{0}(\alpha)\subseteq AC^{0}(m, \alpha)\subseteq TC^{0}(\alpha)\subseteq NC^{1}(\alpha)\subseteq AC^{1}(\alpha)\subseteq\cdots\subseteq P(\alpha)$$AC^{0}(m),$ $TC^{0},$ $NC^{1}$の $AC^{0}$完全問題は，それぞれの相対化の$AC^{0}(\alpha)$

補題 2.
$AC^{0}(m, \alpha)=AC^{0}(MODm, \alpha)$,$TC^{0}(\alpha)=AC^{0}($THRESH,$NC^{1}(\alpha)=AC^{0}($FORMVAL,$\alpha)$,$\alpha)$.

.

完全問題である．

39

3 対数領域階層の相対化
二つの神託$\alpha,$$\beta$を持ち (非) 決定的に動作する機械 $M$ を以下の用に定義する．
$M$ は読み込み専の用の入カテープと，読み書き可能な作業テープ，および 2 本の書き込み専用の質問テープ
4 本のテープを持つ． がに対する質問を行う際， (resp. ) のみが消去される．
$T_{\alpha},$$M$$\alpha(resp.

\beta)$$T_{\alpha}$$T_{\beta}$$T_{\beta}$

また非決定性機械は [5] と同様に，どちらかの質問テープが空でないとき決定的に動作するよう制限する．対数領域階層の相対化$LH(\alpha)$と NLHを以下のように定義する．

$(\alpha)$$LH_{0}(\alpha)=L,$$LH_{i+1}(\alpha)=L(\alpha, LH_{i}(\alpha))$$LH(\alpha)=\bigcup_{i\in N}LH_{i}(\alpha)$,,$NLH_{0}(\alpha)=NL,$$NLH_{i+1}(\alpha)=NL(\alpha, NLH_{i}(\alpha))$

NLH
ただし$L(\alpha, \beta)$$( \alpha)=\bigcup_{i\in N}NLH_{i}(\alpha)$と $NL(\alpha, \beta)$ は二っの神託$\alpha,$$\beta$,.

を持ち作業テープを使用領域が $o(\log(n))$ で (非)決定的に動作する機械にょって計算されるクラス．
定理 3.
$NC^{1}(\alpha)\subseteq LH(\alpha)\subseteq$$NC$

NLH$(\alpha)\subseteq AC^{1}(\alpha)$.

l 回路の値は出力からの深さ優先探索を行うことで対数領域で計算可能．2 つ目の包含関係は定義より自明．3 つ目の包含関係は次の定理より導かれる．
定理 4.
$LH(\alpha)=AC^{0}(1-$STCONN,NLH $(\alpha)=AC^{0}($ STCONN,$\alpha)$$\alpha)$,.

証明は次のページで行う．この定理より [1] と同様に以下の系等が示される．
系 5.

以下の任意の 2 つのクラスについて，もしこれらを分離する神託 が存在するならば，対応$\alpha$する相対化されていないクラスも分離される．
$AC^{0}(m, \alpha)\subseteq TC^{0}(\alpha)\subseteq NC^{1}(\alpha)\subseteq LH(\alpha)\subseteq$

NLH$(\alpha)$

証明．非相対化クラス同士が等しければ，対応する完全問題が互いに $AC$ O 還元可能．よって対応する相対化計算量クラスも等しい．

口

階層全体が補集合を取る操作で閉じていることは自明であるが，各階層においても補集合を取る操作で閉じている．

40系 6 (相対化版 Immerman-Szelepcs\’enyi’ の定理 [3] [7]).
$NLH_{i}(\alpha)=co-NLH_{i}(\alpha)$

完全．
多対一還元のもとで証明． を任意の言語とする．STCONN は$NL(\alpha, \beta)=$. 逆も同様の議論から言えるため，
STCONN $\in cxNL$ より
口$co-NL(\alpha, \beta)$ . よって任意のについて $NLH_{i}(\alpha)=co-NLH_{i}(\alpha)$ .
$\alpha,$$NL(\alpha, \beta)$$L(\alpha, \beta)$$\beta$$NL(\alpha, \beta)\subseteq co-NL(\alpha, \beta)$$i$$L^{2}H(\alpha)$

は作業テープの使用領域が $O(\log^{2})$ , 質問テープの使用領域が $n^{0(1)}$ で抑えられる決定性神託機械の階層によって定義される計算量クラスとして定義する．
系 7 (相対化版 Savitch の定理 [6]).

NLH

証明．STCONN$\in L^{2},$$AC^{0}(\alpha)\subseteq LH(\alpha)$$(\alpha)\subseteq L^{2}H(\alpha)$より，任意の$AC^{0}($STCONN,$\alpha)$

回路の値は $L^{2}H(\alpha)$

で計算可能

口定理 4 の証明．NLH $(\alpha)=AC^{0}($ STCONN,$\alpha)$$LH(\alpha)=AC^{0}(1-$ STCONN,のみ示す．

も同$\alpha)$様にして示される．

(1) NLH
深さが高々$(\alpha)\supseteq AC^{0}($$i$STCONN,$\alpha)$である $AC^{0}($ STCONN,$\alpha)$

回路によって計算される言語は NLHiと帰納的に示す．深さ 1 の回路，つまり AND, $OR$ , NOT, STCONN,$\alpha$$(\alpha)$に含まれるこゲートの計算はすべて$i>1$ のとき，出力のゲートに対する入力はそれぞれ高々深さ $i-1$ の部分回に含まれる．
路によって計算されているため $NLH_{i-1}(\alpha)$ に含まれる．よって出力に対する各入力の値を神託に$NL(\alpha)$

質問することで，出力ゲートの値は計算可能．
STCONN,(2) NLH$NLH_{i}(\alpha)\subseteq
AC^{0}($ STCONN,以下の主張から$(\alpha)\subseteq AC^{0}($主張 8. 任意の神託$\beta$$\alpha)$を帰納法により示す．

$\alpha)$について，$NL(\alpha, \beta)\subseteq AC^{0}($STCONN,$\alpha, \beta)$$i=0$ のとき，STCONN は $AC^{0}$ 還元で $NL$ 完全であるため，NLHo $(\alpha)\subseteq AC^{0}($ STCONN) .
$NLH_{i}(\alpha)\subseteq AC^{0}($STCONN,$\alpha)$と仮定すると，$NLH_{i+1}(\alpha)=NL(\alpha, NLH_{i}(\alpha))$$\subseteq NL(\alpha, AC^{0}($任意の$i$STCONN,$\alpha)$$\subseteq AC^{0}($STCONN,$\alpha, AC^{0}($$=AC^{0}($STCONN,$\alpha)$について $NLH_{i}(\alpha)\subseteq AC^{0}($ STCONN,$\alpha)$)STCONN,$\alpha)$).

なので，NLH$(\alpha)\subseteq AC^{0}($STCONN,$\alpha)$.

主張 8 を示す前に，二つの神託を持つ非決定性対数領域機械 $M$ は以下の制限を満たす同値な機械 $M’$ が存在することを示す．

41
仮定． の質問テープに書き込むとき， の質問テープが空でなければ，次に$\alpha$$\beta$で， への書き込みおよび への質問を行わない． と$T_{\beta}$$\beta$$\alpha$$M$$M’$ はから上記の制限を満たす $M’$ を構成する．

$M$を模倣する．空のらまたはに書き込むとき$T_{\beta}$

へ質問を行うまで$\beta$$T_{\alpha}\neq\epsilon$$\beta$$T_{\alpha},$$\alpha$への質問を行うまを入れ替えても同様．

が空であるかをテープに記録しなが$T_{\beta}$

ならばその実行状態$u$を保存し，$M$ が次に$M$ が先にへの書き込みを行わずに $M$ を模倣する．

$T_{\beta}$$\beta$$\alpha$へ質問を行うとき， は今度は への書き込みを行わずに から $M$ の模倣を続け へ質問を行い， の模倣を続ける． が先に への質問を行うとき， への質問を行いその答えを保存し，今度は へ$M’$$T_{\alpha}$

$u$

$M$

$\alpha$の書き込みを行わずにる．空の$T_{\alpha}$

$u$

$M$

$\beta$$\alpha$$T_{\alpha}$から $M$ の模倣を続け， への質問は保存された答えを用いて $M$ を模倣す$\alpha$に書き込むとき$T_{\beta}\neq\epsilon$

ならば， と$\beta$$\alpha$を入れ替えて同様に動作する．

質問テープが空であるかの記録，実行状態の記録，神託の答えの記録はすべて $o(\log(n))$ 領域で可能であるため，$M’$ は対数領域で動作する．このように動作する $M’$ は確かに上記の仮定を満た$M$ と同値である．
し，主張 8 を示す．基本的な方針として 2 つの神託を持つ対数領域機械$M^{\alpha,\beta}(x)$の実行状態を頂点が を受理する計算パスが存在するか判定する．しかとする計算グラフを構成することで，し質問テープの多項式サイズであるため，実行状態に質問テープの状態を含めると計算グラフの頂$M^{\alpha,\beta}$点数が指数サイズになってしまう．そこで$x$$M^{\alpha,\beta}(x)$の質問テープが空である実行状態のグラフ $G$を構成する．内部状態と作業テープ，ヘッドの位置の組を対数領域非決定性二神託機械(部分) 実行状態と定義すると，長さ の入カに対しての部分実行状態の数を抑える多項式$M^{\alpha,\beta}(x)$の$p$が$M$$n$存在する．
$u_{1}=$$G^{0}$を$\alpha$$u$から次にある$u’$$\alpha$$u$$\ldots,$$u_{p(n)}$$\beta$$u’$$u$へ枝をはる．このようなテープが空で$M^{\alpha_{\}}\beta}(x)$$u_{3},$

テープが共に空でない実行状態への遷移グラフとする．つまりであり， から へ神託への質問を行わずに決定的に遷移するとき，テープと部分実行状態

START, $u_{2}=$ ACCEPT,$\beta$$G^{0}$が次に到達するの頂点は$G^{0}$においては $x$ を入カとする $AC^{0}$ 回路で計算可能．

テープが空でない状態への遷移グラフ$\alpha$$G^{0}$

テープが空で$\beta$$G^{\alpha}$を定義する．実行状態が$u$

でテープが空でない実行状態 $u’$ は以下のいずれかを満たす．

1.
2.

$u$から $u’$ へ決定的に遷移する$u$は$\alpha$

テープヘ書き込みを行い，決定的に遷移して次の$\alpha$へ神託への質問を行った結果 $u’$へ至る．

を質問した結果の遷移なので，回路で計算可能．2の完全な実行状態を部分実行状態と テープの状態， テープの状態

1 は遷移テーブルによる遷移かの条件をみたすとき，$M^{\alpha,\beta}$$\alpha$へ$AC^{0}(\alpha)$$\epsilon$$\alpha$$\beta$の組みで表すと，仮定より次のような実行パスが存在する．
$(u, \epsilon, Q^{\beta}), (v_{0}, Q_{0}^{\alpha}, Q^{\beta}), \ldots, (v_{n}, Q_{n}^{\alpha}, Q^{\beta}), (u’, \epsilon, Q^{\beta})$

ただしから$\alpha$

かつテープの内容で，の質問テープが空でない状態の質問を構成し始めているため，仮定にょり上記の実行パスでは の質問テープへの書き$Q_{i}^{\alpha},$$Q^{\beta}$

は$\alpha,$$\beta$$Q_{i}^{\alpha}\neq\epsilon$$Q^{\beta}\neq\epsilon.$$\beta$$\beta$42
込み及び質問を行わないため， の質問テープの内容はのまま変化しない．上記のようなパはとを入力とするスが存在することと STCONN $(u, v_{n}, G^{0})=1$ は同値であり，質問$Q^{\beta}$$\beta$$AC^{0}($STCONN,$\alpha)$回路で計算可能．よって$G^{\alpha^{arrow}}$

は $x$ を入力とする $AC^{0}($ STCONN,算可能． も同様に定義すると，同様の議論によって$G^{\beta}$$G^{0}$$x$$Q_{n}^{\alpha}$を入力とする $AC^{0}($ STCONN,$x$回路で計$\alpha)$$\beta)$回路で計算可能であることが示される．

最後に質問テープが空である実行状態のグラフ $G$ を構成する．質問テープが空で実行状態がである

1.

2.
3.

$M^{\alpha,\beta}.(x)$$u$が次に到達する質問テープが空である実行状態 $u’$ は以下のいずれかを満たす．

$u$は質問テープへの書き込みを行わず， へ遷移する．

$u$は$\alpha$$u$は$\beta$$u’$

テープヘ書き込みを行い，決定的に遷移して次のテープヘ書き込みを行い，決定的に遷移して次の1 は遷移テーブルによる遷移か算可能． と$u$$u’$

または$\alpha$$\alpha$へ質問を行った結果 $u’$ へ至る．

$\beta$へ質問を行った結果 $u’$ へ至る．

へ空文字の質問による遷移なので，$AC^{0}(\alpha, \beta)$$\beta$回路で計が 2 の条件をみたすとき，仮定より次のような実行パスが存在する．
$(u,\epsilon,\epsilon), (v_{0}, Q^{\alpha}, \epsilon), \ldots, (v_{n}, Q_{n}^{\alpha}, \epsilon), (u’, \epsilon, \epsilon)$

ただし$Q_{i}^{\alpha}$は$\alpha$

テープに書かれた質問で，$Q_{i}^{\alpha}\neq\epsilon$.

また$v_{i}$

はへ決定的に遷移する$v_{i+1}$

至る．後者の遷移が行われるととを入力とす
き仮定より $Qt=Q_{i+1}$ がなりたつ．上記のようなパスが存在するかはか$\searrow$または$\beta$への質問を構成しへ質問をおこなって$\beta$$v_{i+1}$$G^{\alpha}$$x$

STCONN,回路で判定可能であり，パスも同様にして計算できるので， はは を入力とする

る$AC^{0}($$\beta)$$v_{0},$$G$

STCONN START, ACCEPT, $G)$
$($

$X$

$=M^{\alpha,\beta}(X)$$\ldots,$$v_{n}$$AC^{0}($から$Q_{n}^{\alpha}$

STCONN,は構成可能．条件 3$\alpha, \beta)$

回路で計算可能．

より主張 8 は証明された．□

3.1 定数深さ分岐機械による相対化
分岐機械とは，自身の実行状態のコピーを作成しその結果を受け取る特別な操作フォークを行う
状態を持つ．分岐機械の内部状態がであるとき，実行状態がコピーされる．コピー元を$q_{fork}$$q_{f_{or}k}$

親プロセス，コピーを子プロセスと呼ぶ．親プロセス、の内部状態は，子プロセスが受理されるときに遷移する．あるプロセスのフオークの深さを，最初に実行さ卿 Es に遷移し，そうでないとき$q_{NO}$れるプロセスを 1, 深さ$d$のプロセスの子プロセスを $d+1$ として定義する．定数深さ分岐機械とは，フオークの深さが定数で抑えられる分岐機械である．
対数領域で (非) 決定的に動作し，分岐の深さが高々 である分岐機械によって受理される言語$i$を $LF_{i}$ と $NLF_{i}$$NLF_{1}=$ $NL$
$LF$

する．と表記し，$LF$

より，NLF$=$$= \bigcup_{i}LF_{i},$NLHと NLF の相対化を $LF(\alpha)$$NLF_{i}=\cup\iota^{NLF}t$と定義する．

. また $LF$ $=L$ は自明．と NLFと定義する．ただし NLF$=$$NLF_{i}\subseteq_{\backslash }NLH_{i}$かつ$NL$$(\alpha)$$(\alpha)$

は $RST$ 制限を考慮

43
定理 9.
$LF(\alpha)=AC^{0}(1-$STCONN,

NLF $(\alpha)=AC^{0}($ STCONN,

この定理により系 5 から系 7 と同等の系が，$LF(\alpha)$

証明．NLF $(\alpha)=AC^{0}($ STCONN,$\alpha)$, NLF$\alpha)$$\alpha)$$(\alpha)$においても言える．

のみ示す．$LF(\alpha)=AC^{0}(1-$ STCONN,$\alpha)$も同様にして示される．

(1) NLF

STCONN,回路を出力から深さ優先探索しながらゲートの値を求めていく．神託ゲートの各入力を出力とする部分回路は，神託ゲートのネストの深さが高々 $i-1$ なので深さ $i-1$ の分岐機械で計算可能．
(2) NLF
STCONN,$(\alpha)\supseteq AC^{0}($$\alpha)$$(\alpha)\subseteq AC^{0}($$\alpha)$

分岐機械の実行状態のグラフを構成する．対数領域非決定性定数深さ分岐機械
実行状態とは，内部状態と作業テープ，ヘッドの位置の組とする．長さ実行状態の数を抑える多項式態$u$の分岐を行う$i$

START, $u_{2}=$ ACCEPT,$M^{\alpha}(x)$の集合であり，辺集合$E_{i}$の (部分)の入力に対して $M$ の部分$n$が存在する．

$p$$u_{1}=$

高々深さ$M^{\alpha}(x)$$\ldots,$$u_{p(n)}$を構成する． の頂点集合 は部分実行状の次のクエリが空な実行状態であるとき，つまり との計算グラフ

は $u’$ が $u$$u_{3},$$G_{i}$$G_{i}$$V_{i}$$u$$v’$

が以下のいずれかを満たすとき $(u, u’)\in E_{i}.$

1.

2.
3.

$u$

$u$

$u$

は分岐もクエリテープへの書き込みも行わず， へ遷移する．
は分岐を行い， へ遷移する;
はクエリテープに書きこみ，決定的に遷移して神託へ質問を行った結果
$u’$

$u’$

ただし分岐の深さは高々$i$$u’$に至る．

$RST$ 制限よりクエリテープが空でなければ決定的に動作するたとする．

め，実行状態 がクエリテープに書きこみを行うのであれば実行状態 から構成されるクエリは一つに定まり， から質問を構成して神託へ尋ねた結果至る実行状態 はーつに定まる．
$u$

$u$

$u’$

$u$

上記の$u’$$G_{i}$

において，$M^{\alpha}(x)$へ高々深さ

よって深さ$h$$i$の非決定性分岐機械 $M$ と神託が成り立つ．つまりSTCONN,帰納法によりの枝集合$E_{i}$$u$からクエリテープが空の実行状態のフォークを行い到達可能であることと STCONN $(G_{i}, u, u’)=1$ は同値である．

STCONN$AC^{0}($がクエリテープが空の実行状態$\alpha)$$G_{i}$$G_{h}$

が$x$$(G_{h},$$\alpha$について

START, ACCEPT)$=1\Leftrightarrow M^{\alpha}(x)$を入力とする $AC^{o}($ STCONN,$\alpha)$

は受理回路で計算可能ならば，NLF$(\alpha)\subseteq$.
が$x$を入力とする $AC^{0}($ STCONN,を上記の条件にあわせて$E_{i}^{1},$$E_{i}^{2},$$E_{i}^{3}$回路で計算可能であることを示す．
回路に分割し，それぞれが を入力とする$G_{i}$$\alpha)$$x$で計算可能であることを示す． は有限サイズの遷移テーブルを確認すれば良いのでする $AC$ O 回路で計算可能．
$E_{i}^{1}$$AC^{0}$$x$を入力と44が $AC^{0}($ STCONN,$E_{i}^{2}$$\alpha)$回路で計算可能であることを示す．$i=0$ のとき$E_{0}^{2}=\emptyset.$$u$がフォークを行う実行状態のとき，$(u, u’)\in E_{i}^{2}$ を満たす は STCONN $(G_{i-1}, u,$ ACCEPT) より計算可
はとを入力とする(STCONN) 回路で計算でき，帰納法の仮定により
能．よって
$u’$

$x$

$E_{i}^{2}$$x$$AC^{0}$$G_{i-1}$を入力とする $AC^{0}($ STCONN,が $AC^{0}($ STCONN,$E_{i}^{3}$$\alpha)$$\alpha)$で計算可能．

回路で計算可能であることを示す．の判定には， から$(u, u’)\in E_{i}^{3}$$u$♂への決定的な計算パスの存在判定と，その計算パスで構成されるクエリの計算が必要である．そこでグラフ$G_{i}^{q}-$を実行状態を頂点とし， と$u$$u’$が以下のいずれかを満たすときから $u’$ へ辺があ$u$るグラフとして定義する．

1.
2.

は分岐を行わず，決定的に$u$は分岐を行い $u’$ へ遷移する．

1 の枝集合は$E_{i}^{1}$

STCONN,$u’$と同様に $AC^{0}$ 回路で計算可能．2 の枝集合は$E_{i}^{2}$と等しい．よってはで計算可能．実行状態 から構成されるクエリ
は を入力とする(STCONN) 回路で計算可能であるため，よって$AC^{0}($$AC^{0}$へ遷移する;$u$$Q_{u}$$u$$\alpha)$$E_{i}^{2}$

$X$

計算可能

$X$と

$G_{i}^{q}$$AC^{0}($$G_{i}^{q}$はを入力とする

STCONN,$\alpha)$

で
口

参考文献
[1] K. Aehlig, S. Cook, and P. Nguyen. Relativizing small complexity classes and their theories.

In Computer Science Logic, pages 374-388. Springer, 2007.
[2] J.F. Buss. Relativized alternation and space-bounded computation. Joumal of Computerand System Sciences, $36(3):351-378$ , 1988.

[3] N. Immerman. Nondeterministic space is closed under complementation. SIAM Joumal

on computing, $17(5):935-938$ , 1988.
[4] R.E. Ladner and N.A. Lynch. Relativization of questions about
space computabihty.
Theory of Computing Systems, $10(1):19-32$ , 1976.
[5] W.L. Ruzzo, J. Simon, and M. Tompa. Space-bounded hierarchies and probabilistic computations. Joumal of Computer and System Sciences, $28(2):216-230$ , 1984.
$\log$.[6] W.J. Savitch. Relationships between nondeterministic and deterministic tape complexities.

Joumal of computer and system sciences, $4(2):177-192$ , 1970.
[7] R. Szelepcs\’enyi. The method of forced enumeration for nondeterministic automata. Acta
Informatica, $26(3):279-284$ , 1988.

[8] C.B. Wilson.

$A$measure of relativized space which is faithful with respect to depth. Joumalof Computer and System Sci\’ences, $36(3):303-312$ , 1988.