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內。我們已知:

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

LOWER-ELEMENTARY EXPTIME ELEMENTARY PR

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.