計算木

計算木とは、指定された入力に対する非決定性チューリングマシンの計算ステップの表現である。 ^[1]計算木は、ノードとエッジからなる根付き木である。木の各ノードは単一の計算状態を表し、各エッジは次の計算への遷移を表す。木のノード数は木のサイズであり、ルートから特定のノードまでのパスの長さはノードの深さである。出力ノードの最大深さは木の深さである。木の葉は出力ノードと呼ばれる。

決定問題における計算木において、各出力ノードにはYesまたはNoのラベルが付けられる。入力空間Xを持つ木Tにおいて、xへのパスがyesラベルのノードで終わる場合、入力xは受け入れられる。そうでない場合は拒否される。^[2] $x\in X$

与えられた入力に対する計算木の深さは、その入力に対するチューリングマシンの計算時間である。 ^[1]

計算木は計算幾何学や実数計算における問題の計算複雑さの研究にも使われてきた。^[3]^[4]

参考文献

^ ab Griffor, ER (1999), 計算可能性理論ハンドブック, 論理学と数学の基礎研究, 第140巻, エルゼビア, p. 595, ISBN 9780080533049。
^ モレ、バーナード ME (1998)、『計算理論』、アディソン・ウェスレー、338 ページ、ISBN 9780201258288。
^ Ben-Or, M. (1983)、「代数計算木の下限値」、Proc. 15th Annu. Symp. Theory of Computing、pp. 80– 86、doi : 10.1145/800061.808735、ISBN 0-89791-099-0。
^ Grigoriev, Dima; Vorobjov, Nicolai (1996), 「初等超越関数ゲートを用いた計算木の計算量下限値」Theor. Comput. Sci. , 157 (2): 185– 214, doi : 10.1016/0304-3975(95)00159-X。

[hct-1] Griffor, ER (1999), 計算可能性理論ハンドブック, 論理学と数学の基礎研究, 第140巻, エルゼビア, p. 595, ISBN 9780080533049。

[2] モレ、バーナード ME (1998)、『計算理論』、アディソン・ウェスレー、338 ページ、ISBN 9780201258288。

[3] Ben-Or, M. (1983)、「代数計算木の下限値」、Proc. 15th Annu. Symp. Theory of Computing、pp. 80– 86、doi : 10.1145/800061.808735、ISBN 0-89791-099-0。

[4] Grigoriev, Dima; Vorobjov, Nicolai (1996), 「初等超越関数ゲートを用いた計算木の計算量下限値」Theor. Comput. Sci. , 157 (2): 185– 214, doi : 10.1016/0304-3975(95)00159-X。