computer science

R (complexity)

R (complexity) is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand R (complexity) rather than just read about it. In short: 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). 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 grap…

Key takeaways

R (complexity) belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect R (complexity) to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of R (complexity) from memory before moving on to harder problems.

Reference excerpt

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

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

Worked examples

Example 1 — a first encounter with R (complexity)

Start with the simplest possible case. Write down what R (complexity) claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to R (complexity) before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about R (complexity) ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of R (complexity)

In research: R (complexity) appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses R (complexity) in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: R (complexity) is common in secondary-school and first-year university syllabi. It links to neighbouring topics Complexity classes, Computability theory, Theoretical computer science stubs, so understanding it makes those chapters shorter.
In everyday life: Look for R (complexity) outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study R (complexity) in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what R (complexity) means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain R (complexity) out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is R (complexity) in simple terms?

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). Equivalent formulations R is equivalent to the set of all total computable functions in the sense that: a decision pro…

Why does R (complexity) matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study R (complexity)?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on R (complexity).