PR (complejidad)

PR es la clase de complejidad de todas las funciones recursivas primitivas —o, equivalentemente, el conjunto de todos los lenguajes formales que pueden resolverse en un tiempo limitado por dicha función—. Esto incluye la suma , la multiplicación , la exponenciación , la tetración , etc.

La función de Ackermann es un ejemplo de una función que no es recursiva primitiva, lo que demuestra que PR está estrictamente contenida en R (Cooper 2004:88).

Por otro lado, podemos "enumerar" cualquier conjunto recursivamente enumerable (véase también su clase de complejidad RE ) mediante una función recursiva primitiva en el siguiente sentido: dado un input${\displaystyle (M,k)}$, dónde${\displaystyle M}$es una máquina de Turing y${\displaystyle k}$es un número entero, si${\displaystyle M}$paradas dentro${\displaystyle k}$pasos y luego salida${\displaystyle M}$; de lo contrario, no produce nada. Entonces la unión de las salidas, sobre todas las entradas posibles (${\displaystyle M}$, ${\displaystyle k}$), es exactamente el conjunto de${\displaystyle M}$esa parada.

PR contiene estrictamente ELEMENTARY .

PR no contiene problemas "PR-completos" (suponiendo, por ejemplo, reducciones que pertenecen a ELEMENTARY).

La clase PR se puede dividir en una jerarquía infinita de niveles de complejidad cada vez mayores, según la jerarquía de rápido crecimiento .

El${\displaystyle {\text{F}}_{0}}$clase es la clase de problemas que se pueden resolver en${\displaystyle n+O(1)}$tiempo. Es decir, existe una máquina de Turing y una constante${\displaystyle C}$, de tal manera que, dado un input de longitud${\displaystyle n}$, la máquina lo resuelve y se detiene dentro${\displaystyle n+C}$pasos.

El${\displaystyle {\text{F}}_{1}}$clase es la clase de problemas que se pueden resolver en${\displaystyle {\mathsf {poly}}(n)}$tiempo.

El${\displaystyle {\text{F}}_{2}}$La clase es ELEMENTAL.

El${\displaystyle {\text{F}}_{3}}$La clase es TOWER, que puede escribirse de forma equivalente como la clase de problemas que pueden resolverse en tiempo tetracional .

El sindicato${\displaystyle \bigcup _{n\in \mathbb {N} }{\text{F}}_{n}}$es relaciones públicas.

En la práctica, muchos problemas que no están en las relaciones públicas sino que están justo más allá de ellas son${\displaystyle {\text{F}}_{\omega }}$-completo (Schmitz 2016).

• S. Barry Cooper (2004). Teoría de la computabilidad . Chapman & Hall. ISBN 1-58488-237-9.
• Herbert Enderton (2011). Teoría de la computabilidad . Academic Press. ISBN 978-0-12-384-958-8.
• Schmitz, Sylvain (2016). "Jerarquías de complejidad más allá de lo elemental". ACM Transactions on Computation Theory . 8 : 1–36 . arXiv : 1312.5686 . doi : 10.1145/2858784 . S2CID 15155865 . 

• Complexity Zoo : PR .