Jump to content

R (complexity)

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by JCW-CleanerBot (talk | contribs) at 19:51, 25 March 2021 (task, replaced: Bulletin (New Series) of the American Mathematical Society → Bulletin of the American Mathematical Society |series=New Series). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In computational complexity theory, R is the class of decision problems solvable by a Turing machine, which is the set of all recursive languages (also called decidable languages).

Equivalent formulations

R is equal to the set of all total computable functions.

Relationship with other classes

Since we can decide any problem for which there exists a recogniser and also a co-recogniser by simply interleaving them until one obtains a result, the class is equal to RE ∩ co-RE.

References

  • Blum, Lenore, Mike Shub, and Steve Smale, (1989), "On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines", Bulletin of the American Mathematical Society, New Series, 21 (1): 1-46.

Complexity Zoo: Class R


P ≟ NP 

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=R_(complexity)&oldid=1014209327"