Jump to content

R (complexity)

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Wylie39 (talk | contribs) at 04:03, 29 March 2020 (Reverted edits by 92.6.7.172 (talk) to last version by D.Lazard). 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.

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. "On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines." Bulletin (New Series) of the American Mathematical Society 21.1 (1989): 1-46.

External links

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=947910511"