誠実性定理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/12/14 23:42 UTC 版)
「ギャップ定理 (計算複雑性理論)」の記事における「誠実性定理」の解説
複雑性クラスは C ( t ) {\displaystyle \mathrm {C} (t)} と表されるが、名前 t {\displaystyle t} には複数の取り方がある。時間階層定理や空間階層定理は、構成可能性という良い性質を持つ関数で名付けられた複雑性クラスは、ある大きさを超えるギャップを持たないことを示している。抽象複雑性においても、誠実性（英: honestness）と呼ばれる良い性質を持つ関数で名付けられた複雑性クラスにはギャップ現象が生じないことが知られている。誠実性はその関数の計算複雑性が入力と出力に対して大きすぎないという性質である。McCraightとMeyerは計算可能関数で命名された複雑性クラスは誠実な関数に改名できることを証明した。これはギャップ定理が複雑性クラスの命名によって生じるものであることを示している。
※この「誠実性定理」の解説は、「ギャップ定理 (計算複雑性理論)」の解説の一部です。
「誠実性定理」を含む「ギャップ定理 (計算複雑性理論)」の記事については、「ギャップ定理 (計算複雑性理論)」の概要を参照ください。
ウィキペディア小見出し辞書の「誠実性定理」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 誠実性定理のページへのリンク
