PR (complexity)

PR is the complexity class of all <a href="/facts/Primitive_recursive_function/4z97gRnl">primitive recursive functions</a>—or, equivalently, the set of all <a href="/facts/Formal_language/crDTyP8q">formal languages</a> that can be decided in <a href="/facts/Time_complexity/77T62gmf">time</a> bounded by such a function. This includes <a href="/facts/Addition/apFWJBFB">addition</a>, <a href="/facts/Multiplication/VtcUjpNv">multiplication</a>, <a href="/facts/Exponentiation/pac6QY2g">exponentiation</a>, <a href="/facts/Tetration/5rKeVVYv">tetration</a>, etc.
The <a href="/facts/Ackermann_function/WQNpCWHn">Ackermann function</a> is an example of a function that is not primitive recursive, showing that PR is strictly contained in <a href="/facts/R_(complexity)/RRLVW00j">R</a> (Cooper 2004:88).
On the other hand, we can "enumerate" any <a href="/facts/Recursively_enumerable_set/lpzr8jHn">recursively enumerable set</a> (see also its complexity class <a href="/facts/RE_(complexity)/lqtossYw">RE</a>) by a primitive-recursive function in the following sense: given an input 
 
 
 
 (
 M
 ,
 k
 )
 
 
 {\displaystyle (M,k)}
 
, where 
 
 
 
 M
 
 
 {\displaystyle M}
 
 is a <a href="/facts/Turing_machine/ojCtglYu">Turing machine</a> and 
 
 
 
 k
 
 
 {\displaystyle k}
 
 is an integer, if 
 
 
 
 M
 
 
 {\displaystyle M}
 
 halts within 
 
 
 
 k
 
 
 {\displaystyle k}
 
 steps then output 
 
 
 
 M
 
 
 {\displaystyle M}
 
; otherwise output nothing. Then the union of the outputs, over all possible inputs (
 
 
 
 M
 
 
 {\displaystyle M}
 
, 
 
 
 
 k
 
 
 {\displaystyle k}
 
), is exactly the set of 
 
 
 
 M
 
 
 {\displaystyle M}
 
 that halt.
PR strictly contains <a href="/facts/ELEMENTARY/rW6PWu4E">ELEMENTARY</a>.
PR does not contain "PR-complete" problems (assuming, e.g., <a href="/facts/Many-one_reduction/YUKNlYPh">reductions</a> that belong to ELEMENTARY).

PR (complexity) open-in-new

PR (complexity)