加速定理との関係
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/12/14 23:42 UTC 版)
「ギャップ定理 (計算複雑性理論)」の記事における「加速定理との関係」の解説
本来のギャップ定理は上記のものよりも強い次の主張である： Φ {\displaystyle \Phi } を抽象複雑性測度とする。任意の全域計算可能関数 g {\displaystyle g} で g ( x ) ≥ x {\displaystyle g(x)\geq x} なるものに対して、強単調な全域計算可能関数 t {\displaystyle t} が存在して、 t {\displaystyle t} と g ∘ t {\displaystyle g\circ t} を制限とする指標の全体が一致する。 これによれば t {\displaystyle t} と g ∘ t {\displaystyle g\circ t} との間の複雑さを持つ指標はそもそも存在しないから、複雑さ g ∘ t {\displaystyle g\circ t} 程度で計算可能な関数で複雑さ t {\displaystyle t} 程度でも計算可能なものが存在する、というわけではない。したがってギャップ定理は加速定理ではない。
※この「加速定理との関係」の解説は、「ギャップ定理 (計算複雑性理論)」の解説の一部です。
「加速定理との関係」を含む「ギャップ定理 (計算複雑性理論)」の記事については、「ギャップ定理 (計算複雑性理論)」の概要を参照ください。
ウィキペディア小見出し辞書の「加速定理との関係」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 加速定理との関係のページへのリンク
