跳转到内容

ELEMENTARY

维基百科,自由的百科全书

計算複雜度理論裡面,複雜度類ELEMENTARY是所有指數譜系裡面的複雜度類聯集:

這名稱最早是為了探討可計算函數不可判定問題,由László Kalmár所提出;most problems in it are far from elementary。Some natural recursive problems lie outside ELEMENTARY, and are thus NONELEMENTARY。相當值得注意的,有一些原始遞歸函數問題不在ELEMENTARY內。我們已知:

LOWER-ELEMENTARY EXPTIME ELEMENTARY PR

與ELEMENTARY僅包含有限的(例如,)比較,PR使用的 超運算更一般化(例如,tetration),因此PR不包含於ELEMENTARY。