View source for PR (complexity)

'''PR''' is the complexity class of all [[Primitive recursive function|primitive recursive function]]s—or, equivalently, the set of all [[Formal language|formal language]]s that can be decided in [[Time complexity|time]] bounded by such a function. This includes [[Addition|addition]], [[Multiplication|multiplication]], [[Exponentiation|exponentiation]], [[Tetration|tetration]], etc.
The [[Ackermann function]] is an example of a function that is ''not'' primitive recursive, showing that PR is strictly contained in [[R (complexity)|R]] (Cooper 2004:88).

On the other hand, we can "enumerate" any [[Recursively enumerable set|recursively enumerable set]] (see also its complexity class [[RE (complexity)|RE]]) by a primitive-recursive function in the following sense: given an input (''M'',&nbsp;''k''), where ''M'' is a [[Turing machine]] and ''k'' is an integer, if ''M'' halts within ''k'' steps then output ''M''; otherwise output nothing.  Then the union of the outputs, over all possible inputs (''M'',&nbsp;''k''), is exactly the set of ''M'' that halt.

PR strictly contains [[ELEMENTARY]].

PR does not contain "PR-complete" problems (assuming, e.g., [[Many-one reduction|reduction]]s that belong to ELEMENTARY). In practice, many problems that are not in PR but just beyond are <math>\text{𝐅}_\omega</math>-complete (Schmitz 2016).

== References ==
* {{cite book|author=S. Barry Cooper |year=2004|title=Computability Theory|publisher= Chapman & Hall|isbn=1-58488-237-9}}
* {{cite book|author=Herbert Enderton |year=2011|title=Computability Theory|publisher=  Academic Press|isbn=978-0-12-384-958-8}}
* {{cite journal|arxiv=1312.5686|doi=10.1145/2858784|title=Complexity Hierarchies beyond Elementary|year=2016|last1=Schmitz|first1=Sylvain|journal=ACM Transactions on Computation Theory|volume=8|pages=1–36|s2cid=15155865 }}

==External links ==
* {{ComplexityZoo|PR|P#pr}}.

{{ComplexityClasses}}

{{DEFAULTSORT:Pr (Complexity)}}
[[Category:Complexity classes]]

{{Sourceattribution|PR (complexity)}}