R (complexity): Difference between revisions

Content deleted Content added
No edit summary
 
(25 intermediate revisions by 23 users not shown)
Line 1:
TheIn [[computational complexity theory]], '''R''' is the class of [[decision problemsproblem]]s solvable by a [[Turing machine.]], Oftenwhich identified withis the classset of 'effectivelyall computable'[[recursive functionslanguage]]s (thealso Church-Turingcalled decidable thesislanguages).
 
==Equivalent formulations==
Since we can decide any problem for which there exists a recogniser and also a co-recogniser, the class is equal to <math>RE \cap coRE</math>.
R is equivalent to the set of all total [[computable function]]s 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 of a function|graph]] is in R.
 
==Relationship with other classes==
==See also==
Since we can decide any problem for which there exists a [[recognizer|recogniser]] and also a co-recogniser by simply interleaving them until one obtains a result, the class is equal to <math>[[RE \cap(complexity)|'''RE''']] coRE</math>∩ '''co-RE'''.
*[[Recursive language]]
 
==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==
{{CZoo|Class R|R#r}}
* [http://qwiki.caltech.edu/wiki/Complexity_Zoo#re Complexity Zoo]
{{ComplexityClasses}}
 
[[Category:Complexity classes]]
[[Category:Computability theory]]
 
 
{{ComplexityClasses}}
{{comp-sci-theory-stub}}