計算機械モデル
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/14 02:26 UTC 版)
DTIMEの定義に使われる機械モデルは様々あるが、資源に関する能力に差はない。特に小さい時間クラスを論じる場合、多テープ型のチューリング機械が使われることが多い。多テープ型の決定性チューリング機械は単一テープのチューリング機械に比較しても高々2乗の時間性能の向上にしかならない (Papadimitriou 1994, Thrm. 2.1)。 定数倍の形で表される時間の違いは DTIME によるクラス表現に影響しない。定数倍の性能向上は有限状態制御における状態数を増やすことで実現される。Papadimitriou (1994, Thrm. 2.2) によれば、言語 L について以下のように記されている。 L ∈ TIME ( f ( n ) ) {\displaystyle {\text{L}}\in {\text{TIME}}(f(n))} であるとき、任意の ϵ > 0 {\displaystyle \epsilon >0} について L ∈ TIME ( f ′ ( n ) ) {\displaystyle {\text{L}}\in {\text{TIME}}\left(f'(n)\right)} となる。ここで f ′ ( n ) = ϵ f ( n ) + n + 2 {\displaystyle f'(n)=\epsilon f(n)+n+2} である。
※この「計算機械モデル」の解説は、「DTIME」の解説の一部です。
「計算機械モデル」を含む「DTIME」の記事については、「DTIME」の概要を参照ください。
ウィキペディア小見出し辞書の「計算機械モデル」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 計算機械モデルのページへのリンク
