構築可能な関数

計算複雑性理論において、時間構築可能関数とは、自然数から自然数への関数fであって、 f ( n )をチューリングマシンによってf ( n )の時間で構築できる性質を持つ関数のことである。このような定義の目的は、何らかのチューリングマシンの実行時間の上限を与えない関数を除外することにある。^{[ 1 ]}

チューリングマシンは、記号を含むアルファベットを用いて標準的な方法で定義されるものとする。${\displaystyle 0,1}$入力文字列以外のゼロを含む標準入力テープを備えています。$1^n$文字列を表す${\displaystyle n}$つまり、それは単項表現です。${\displaystyle n}$。 させて${\displaystyle |n|}$バイナリ表現とする。

関数${\displaystyle f}$チューリングマシンが存在する場合、それは時間構築可能と呼ばれる。${\displaystyle M}$計算${\displaystyle M(1^{n})}$停止${\displaystyle O(f(n))}$値を持つステップ${\displaystyle |f(n)|}$。

この定義では、${\displaystyle M(1^{n})=1^{f(n)}}$代わりに、2つは相互変換できるため${\displaystyle O(f(n))}$手順。^{[ 1 ]}

関数${\displaystyle f}$チューリングマシンが存在する場合、空間構築可能と呼ばれる。${\displaystyle M}$そのため${\displaystyle M(1^{n})}$価値を伴う停止${\displaystyle |f(n)|}$（または同等の）${\displaystyle 1^{f(n)}}$)使用中${\displaystyle O(f(n))}$空間。^{[ 1 ]}

同様に、${\displaystyle f}$チューリングマシンが存在する場合、空間構築可能と呼ばれる。${\displaystyle M}$有限個を除くすべての${\displaystyle n}$計算${\displaystyle M(1^{n})}$正確に${\displaystyle f(n)}$セルは空白ではなく、操作中に他のセルに書き込みは行われていない。^{[ 3 ]：定義2.4}これは「完全に空間構成可能」と呼ばれることもある。しかし、この2つの定義は同等である。^{[ 3 ]：定理2.7}

一般的に使用されるすべての機能（例：${\displaystyle n,n^{2},2^{n},n!}$）は時間的にも空間的にも構築可能である。${\displaystyle f(n)=\オメガ (n)}$構造は単純です。例えば、${\displaystyle n^{2}}$は 1 つのネストされた for ループによって構築され、$\displaystyle n^{3}}$は、2 つの入れ子になった for ループなどによって構築されます。

もし${\displaystyle f(n)=o(n)}$時間構築可能であれば、最終的には定数となる。そうでなければ、入力全体を読み込むのに十分な時間がないからである。

${\displaystyle \ln n}$宇宙空間に構築可能であっても${\displaystyle \ln n=o(n)}$。

計算可能な関数すべてについて${\displaystyle f}$計算可能な関数が存在する${\displaystyle g}$それは時間的に構築可能であり、${\displaystyle \forall n,g(n)>f(n)}$[ ^{3 ] ：補題2.3}

時間構築可能関数は、時間階層定理などの計算複雑性理論の結果で使用されます。時間階層定理は、アルゴリズムがf ( n ) ステップ以上経過したかどうかをO ( f ( n )) 時間で判定しなければならないチューリングマシンに依存しているため、これらの関数は重要です。もちろん、その時間内にf ( n )を計算できなければ、これは不可能です。このような結果は通常、すべての自然関数fに対して真ですが、人工的に構築されたfに対しては必ずしも真ではありません。これらの結果を厳密に定式化するには、定理が真となる自然関数 fの厳密な定義が必要です。時間構築可能関数は、このような定義を提供するためによく使用されます。

空間構成可能な関数も同様に使用され、例えば空間階層定理で使用されています。

この記事は、 PlanetMathの constructible の素材を組み込んでおり、Creative Commons Attribution-Share-Alike Licenseの下でライセンスされています。