computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...

, 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 of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...

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

, which is the set of all

recursive language In mathematics, logic and computer science, a formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of t ...

s (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. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can d ...

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 , one has \mathbf_(x)=1 if x ...

is computable, *a total function is computable if and only if its

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

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 Stephen Smale (born July 15, 1930) is an American mathematician, known for his research in topology, dynamical systems and mathematical economics. He was awarded the Fields Medal in 1966 and spent more than three decades on the mathematics facult ...

, (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 {{comp-sci-theory-stub