PR (Complexitat)
En teoria de la complexitat, la classe de complexitat PR és el conjunt de totes les funcions recursives primitives o, equivalentment el conjunt de tots els llenguatges formals que es poden decidir per aquestes funcions.[1][2]
La funció d'Ackermann és un exemple de funció que no és funció recursiva primitiva, mostrant que la classe PR és estrictament continguda a R.
PR conté estrictament la classe ELEMENTARY.[3]
PR no conté els problemes PR-complet.
Referències[modifica]
- ↑ Barry), Cooper, S. B. (S.. Computability theory. Boca Raton: Chapman & Hall/CRC, 2004. ISBN 1584882379.
- ↑ B., Enderton, Herbert. Computability theory : an introduction to recursion theory. Amsterdam: Academic Press, 2011. ISBN 9780123849588.
- ↑ «Complexity Zoo:P - Complexity Zoo» (en anglès). Arxivat de l'original el 2018-01-19. [Consulta: 30 novembre 2018].
| Considerades tractables | |
|---|---|
| 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 | |
| Jerarquia de classes | |
| Families de classes | |
