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 (also called decidable languages).

## Contents

* 1 Equivalent formulations
* 2 Relationship with other classes
* 3 References
* 4 External links

## Equivalent formulations

R is equivalent to the set of all total computable functions in the sense that:

* a decision problem is in R if and only if its indicator function is computable,
* a total function is computable if and only if its graph is in R.

## 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.

## External links

Complexity Zoo: Class R

* v
* t
* e

Important complexity classes (more)

Considered feasible|

* DLOGTIME
* AC0
* ACC0
* TC0
* 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
* 2-EXPTIME
* 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

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/R (complexity). Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=R_(complexity)&oldid=287172"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template