|
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
|
||||||||||||
