Elementarno

U teoriji računarske kompleksnosti, klasa kompleksnosti elementarno, koja se sastoji od elementarnih rekurzivnih funkcija, unija je sledećih klasa:

${\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}}$

Ime klase je postavio László Kalmár, u kontekstu rekurzivnih funkcija i neodlučivosti; većina problema iz ove klase su daleko od elementarnih. Neki prirodni rekurzivni problemi su van elementarne klase, tj oni su neelementarni. Što je najbitnije, postoje primitivni rekurzivni problemi koji nisu u klasi elementarno. Poznato je da važi:

LOWER-ELEMENTARY $\subsetneq$ EXPTIME $\subsetneq$ ELEMENTARY $\subsetneq$ PR $\subsetneq$ R

Dok klasa elementarno sadrži ograničene aplikacije stepenovanja ( na primer ), PR omogućava više generalnih hiper operatora (na rpimer tetracija) koji nisu sadržani u klasi elementarno.

Definicija

Defenicije elementarnih rekurzivnih funkcija su iste kao definicije primitivnih rekurzivnih funkcija, s tim što je primitivna rekurzija zamenjena ograničenim sumiranjem i ograničenim proizvodom. Sve funkcije rade nad prirodnim brojevima. Osnovne funkcije, od kojih su sve elementarno rekurzivne su:

• Nula funkcija. Vraća nulu: f(x) = 0.
• Funkcija naslednika: f(x) = x + 1. Ova funkcija je često označena sa S, tj S(x). Kroz ponavljanje ove funkcije može se postići adicija.
• Funkcije projekcije: koriste se za ignorisanje argumenata. Na primer, f(a, b) =a je funkcija projekcije.
• Funkcija oduzimanja: f(x, y) = x – y ako je y < x , ili 0 ako je y ≥ x. Ova funkcija se koristi za definisanje kondicionala i iteracija.

Iz ovih osnovnih funkcija možemo izvesti druge elementarne rekurzivne funkcije:

• Kompozicija: prosleđivanje vrednosti neke elementarne rekurzivne funkcije kao argument druge elementarne rekurzivne funkcije: f(x₁, ..., x_n) = h(g₁(x₁, ..., x_n), ..., g_m(x₁, ..., x_n)) je elementarno rekurzivno ako je g elementarno rekurzivna funkcija i ako je svako gi elementarno rekurzivna funkcija.
• Ograničeno sumiranje: $f(m,x_{1},\ldots ,x_{n})=\sum \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})$ je elementarno rekurzivna funkcija ako je g elementarno rekurzivna funkcija.
• Ograničen proizvod: $f(m,x_{1},\ldots ,x_{n})=\prod \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})$ je elementarno rekurzivna funkcija ako je g elementarno rekurzivna funkcija.

Niže elementarno rekurzivne funkcije

Niže elementarno rekurzivne funkcije prate prethodno postavljene definicije, osim što ograničen proizvod nije dozvoljen. Ovo znači da niža elementarno rekurzivna funkcija mora biti nula, funkcija naslednik, funkcija projekcije, kompozicija drugih nižih elementarno rekurzivnih funkcija, ili ograničena suma drugih nižih elementarno rekurzivnih funkcija. Dok elementarno rekurzivne funkcije potencijalno imaju više od eksponencijalnog rasta, niže elementarno rekurzivne funkcije imaju polinomijalni rast.

Osnove za klasu Elementarno

Klasa elementarnih funkcija se podudara sa zatvaranjem u odnosu na kompoziciju projekcija i jednog od sledećih setova funkcija: $\{n+1,n\,{\stackrel {.}{-}}\,m,\lfloor n/m\rfloor ,n^{m}\}$, $\{n+m,n\,{\stackrel {.}{-}}\,m,\lfloor n/m\rfloor ,2^{n}\}$, $\{n+m,n^{2},n\,{\bmod {\,}}m,2^{n}\}$, where $n\,{\stackrel {.}{-}}\,m=\max\{n-m,0\}$, gde je prethodno definisana funkcija oduzimanja.

Deskriptivna karakterizacija

U deskriptivnoj kompleksnosti, klasa elementarno je jednaka klasi upita višeg reda. Ovo znači da svaki jezik u elementarno klasi kompleksnostimože biti napisan kao formula višeg reda koja je istinita samo za elemente iz jezika. Preciznije, $\mathrm {NTIME} (2^{2^{\cdots {2^{O(n)}}}})=\exists {}HO^{i}$ , gde $\cdots$ označavaju kulu stepenovanja $i$ i $\exists {}HO^{i}$ predstavlja klasu ušita koji počinju egzistencijalnim kvantifikatorima i-tog reda a zatim formulom (i − 1)-og reda.

Vidi još

Primitivna rekurzivna funkcija