Елементарно

У теорији рачунарске комплексности, класа комплексности елементарно, која се састоји од елементарних рекурзивних функција, унија је следећих класа:

${\displaystyle {\begin{aligned}\mathrm {ELEMENTARY} &=\mathrm {EXP} \cup \mathrm {2EXP} \cup \mathrm {3EXP} \cup \cdots \\&=\mathrm {DTIME} (2^{n})\cup \mathrm {DTIME} (2^{2^{n}})\cup \mathrm {DTIME} (2^{2^{2^{n}}})\cup \cdots \end{aligned}}}$

Име класе је поставио László Kalmár, у контексту рекурзивних функција и неодлучивости; већина проблема из ове класе су далеко од елементарних. Неки природни рекурзивни проблеми су ван елементарне класе, тј они су неелементарни. Што је најбитније, постоје примитивни рекурзивни проблеми који нису у класи елементарно. Познато је да важи:

LOWER-ELEMENTARY ${\displaystyle \subsetneq }$ EXPTIME ${\displaystyle \subsetneq }$ ELEMENTARY ${\displaystyle \subsetneq }$ PR ${\displaystyle \subsetneq }$ R

Док класа елементарно садржи ограничене апликације степеновања ( на пример ), PR омогућава више генералних хипер оператора (на рпимер тетрација) који нису садржани у класи елементарно.

Дефиниција

Дефениције елементарних рекурзивних функција су исте као дефиниције примитивних рекурзивних функција, с тим што је примитивна рекурзија замењена ограниченим сумирањем и ограниченим производом. Све функције раде над природним бројевима. Основне функције, од којих су све елементарно рекурзивне су:

• Нула функција. Враћа нулу: f(x) = 0.
• Функција наследника: f(x) = x + 1. Ова функција је често означена са S, тј S(x). Кроз понављање ове функције може се постићи адиција.
• Функције пројекције: користе се за игнорисање аргумената. На пример, f(a, b) =a је функција пројекције.
• Функција одузимања: f(x, y) = x – y ако је y < x , или 0 ако је y ≥ x. Ова функција се користи за дефинисање кондиционала и итерација.

Из ових основних функција можемо извести друге елементарне рекурзивне функције:

• Композиција: прослеђивање вредности неке елементарне рекурзивне функције као аргумент друге елементарне рекурзивне функције: f(x₁, ..., x_n) = h(g₁(x₁, ..., x_n), ..., g_m(x₁, ..., x_n)) је елементарно рекурзивно ако је г елементарно рекурзивна функција и ако је свако gi елементарно рекурзивна функција.
• Ограничено сумирање: ${\displaystyle f(m,x_{1},\ldots ,x_{n})=\sum \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})}$ је елементарно рекурзивна функција ако је g елементарно рекурзивна функција.
• Ограничен производ: ${\displaystyle f(m,x_{1},\ldots ,x_{n})=\prod \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})}$ је елементарно рекурзивна функција ако је g елементарно рекурзивна функција.

Ниже елементарно рекурзивне функције

Ниже елементарно рекурзивне функције прате претходно постављене дефиниције, осим што ограничен производ није дозвољен. Ово значи да нижа елементарно рекурзивна функција мора бити нула, функција наследник, функција пројекције, композиција других нижих елементарно рекурзивних функција, или ограничена сума других нижих елементарно рекурзивних функција. Док елементарно рекурзивне функције потенцијално имају више од експоненцијалног раста, ниже елементарно рекурзивне функције имају полиномијални раст.

Основе за класу Елементарно

Класа елементарних функција се подудара са затварањем у односу на композицију пројекција и једног од следећих сетова функција: ${\displaystyle \{n+1,n\,{\stackrel {.}{-}}\,m,\lfloor n/m\rfloor ,n^{m}\}}$, ${\displaystyle \{n+m,n\,{\stackrel {.}{-}}\,m,\lfloor n/m\rfloor ,2^{n}\}}$, ${\displaystyle \{n+m,n^{2},n\,{\bmod {\,}}m,2^{n}\}}$, where ${\displaystyle n\,{\stackrel {.}{-}}\,m=\max\{n-m,0\}}$, где је претходно дефинисана функција одузимања.^[1][2]

Дескриптивна карактеризација

У дескриптивној комплексности, класа елементарно је једнака класи упита вишег реда.^[3] Ово значи да сваки језик у елементарно класи комплексностиможе бити написан као формула вишег реда која је истинита само за елементе из језика. Прецизније, ${\displaystyle \mathrm {NTIME} (2^{2^{\cdots {2^{O(n)}}}})=\exists {}HO^{i}}$ , где ${\displaystyle \cdots }$ означавају кулу степеновања ${\displaystyle i}$ и ${\displaystyle \exists {}HO^{i}}$ представља класу ушита који почињу егзистенцијалним квантификаторима i-тог реда а затим формулом (i − 1)-ог реда.

Види још

Примитивна рекурзивна функција

Референце

1. Mazzanti, S., "Plain Bases for Classes of Primitive Recursive Functions", Mathematical Logic Quarterly, 48 (2002) 93–104
2. Marchenkov, S. S. (2007). „Superpositions of elementary arithmetic functions”. Journal of Applied and Industrial Mathematics. 1 (3): 351—360. S2CID 122405814. doi:10.1134/S1990478907030106. 
3. Lauri Hella and José María Turull-Torres (2006), „Computing queries with higher-order logics”, Theoretical Computer Science ((what is called "number" in bibtex) изд.), Essex, UK: Elsevier Science Publishers Ltd., 355 (2): 197—214, ISSN 0304-3975, doi:10.1016/j.tcs.2006.01.009