En teoria de la complexitat, la classe de complexitat ELEMENTARY de les funcions recursives primitives és la unió de les classes[1]
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[2]
- LOWER-ELEMENTARY ⊊ EXPTIME ⊊ ELEMENTARY ⊊ PR ⊊ R
Referències
- ↑ E., Rose, H.. Subrecursion : functions and hierarchies. Oxford [Oxfordshire]: Clarendon Press, 1984. ISBN 0198531893.
- ↑ «Complexity Zoo:E - Complexity Zoo» (en anglès). Arxivat de l'original el 2016-08-27. [Consulta: 30 novembre 2018].
Classes de complexitat |
---|
Considerades tractables | DLOGTIME · AC0 · ACC0 · TC0 · L · SL · RL · NL · NC · SC · CC · P · P-complet · ZPP · RP · BPP · BQP · APX |
---|
Suposadament intractables | UP · NP · NP-complet · NP-hard · co-NP · co-NP-complet · AM · QMA · PH · ⊕P · PP · ♯P · ♯P-complet · IP · PSPACE · PSPACE-complet |
---|
Considerades intractables | EXPTIME · NEXPTIME · EXPSPACE · ELEMENTARY · PR · R · RE · ALL |
---|
Jerarquia de classes | |
---|
Families de classes | |
---|