En teoria de la complexitat, la classe de complexitat ELEMENTARY de les funcions recursives primitives és la unió de les classes
El nom va ser proposat per László Kalmár, en el context de funcions recursives i indecibilitat. Alguns problemes recursius cauen fora de la classe ELEMENTARY i, per tant, son dins de NO-ELEMENTARY. Particularment, hi ha problemes a les classes associades a la recursió primitiva que no està a ELEMENTARY.
Se sap que
LOWER-ELEMENTARY ⊊ EXPTIME ⊊ ELEMENTARY ⊊ PR ⊊ R
Referències
Categoria:Classes de complexitat