Lesson plan

PR (complexity)

PR is the complexity class of all primitive recursive functions—or, equivalently, the set of all formal languages that can be decided in time bounded by such a function. This includes addition, multiplication, exponentiation, tetration, etc. The Ackermann function is an example of a function that is not primitive recursive, showing that PR is strictly contained in R (Cooper 2004:88). On the other hand, we can "enumerate" any recursively enumerable set (see also its complexity class RE) by a primitive-recursive function in the following sense: given an input (M, 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 , k ), is exactly the set of M that halt. PR strictly contains ELEMENTARY. PR does not contain "PR-complete" problems (assuming, e.g., reductions that belong to ELEMENTARY).

Back to article

Article summary

PR is the complexity class of all primitive recursive functions—or, equivalently, the set of all formal languages that can be decided in time bounded by such a function. This includes addition, multiplication, exponentiation, tetration, etc. The Ackermann function is an example of a function that is not primitive recursive, showing that PR is strictly contained in R (Cooper 2004:88). On the other hand, we can "enumerate" any recursively enumerable set (see also its complexity class RE) by a primitive-recursive function in the following sense: given an input (M, 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 , k ), is exactly the set of M that halt. PR strictly contains ELEMENTARY. PR does not contain "PR-complete" problems (assuming, e.g., reductions that belong to ELEMENTARY).

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.