computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

, R is the class of

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...

s solvable by a

Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...

, which is the set of all recursive languages (also called decidable languages).

Equivalent formulations

R is equivalent to the set of all total

computable function Computable functions are the basic objects of study in computability theory. Informally, a function is ''computable'' if there is an algorithm that computes the value of the function for every value of its argument. Because of the lack of a precis ...

s in the sense that: *a decision problem is in R if and only if its

indicator function In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , then the indicator functio ...

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 The ''Bulletin of the American Mathematical Society'' is a quarterly mathematical journal published by the American Mathematical Society. Scope It publishes surveys on contemporary research topics, written at a level accessible to non-experts. ...

'', New Series, 21 (1): 1-46.

External links

Complexity classes Computability theory {{comp-sci-theory-stub