記述的特徴付け
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/03/07 19:04 UTC 版)
「ELEMENTARY」の記事における「記述的特徴付け」の解説
記述計算量の観点から見ると ELEMENTARY は 高階論理 で表されるクラスに一致する。 これの意味することは複雑性クラス ELEMENTARY に属す任意の言語は高階の論理式によって定義可能ということである。もっと正確にいえば N T I M E ( 2 2 ⋯ 2 O ( n ) ) = ∃ H O i {\displaystyle \mathrm {NTIME} (2^{2^{\cdots {2^{O(n)}}}})=\exists {}HO^{i}} が成り立つ。ここで ⋯ {\displaystyle \cdots } は i {\displaystyle i} 個の指数のタワーを表す。また ∃ H O i {\displaystyle \exists {}HO^{i}} は i {\displaystyle i} 階の存在量化から始まり i − 1 {\displaystyle i-1} 階の論理式が続く形の論理式で表される問い合わせと一致する。
※この「記述的特徴付け」の解説は、「ELEMENTARY」の解説の一部です。
「記述的特徴付け」を含む「ELEMENTARY」の記事については、「ELEMENTARY」の概要を参照ください。
ウィキペディア小見出し辞書の「記述的特徴付け」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 記述的特徴付けのページへのリンク
