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.