R (complexity)

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 ∩ coRE.

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

Important complexity classes (more)

Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP APX

Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete

Considered infeasible	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL

Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy

Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

This article is issued from Wikipedia - version of the 12/19/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.