# Computability — Classes of Problems, The Art of Reduction

This is Part 2 of Series: “How To Explain Complexity Theory To Your Buddy”. You can check my all posts here:

There are some different classes of problems in computer science world in terms of computability:

*SD*: Semi-Decidable or Recognizable means that we can assure in *finite* steps if a word is *accepted* by M, but we cannot really assure if a word is rejected. This has mostly the following form:

In the code above, the only way the while loop is left is by setting the result to YES. Otherwise, there is no return value and the result is undefined till a YES instance is found. If only we prove that it is in a *infinite* loop, the result is NO.

We assume that the output is always a YES instance: *If it terminates*, it returns always YES (partially correct), but it is not known *if it always terminates* (not totally correct).

An interesting feature of SD problems is that we can list all outputs (lexicographically) because we know with guarantee that the inputs that are accepted are accepted.

*CSD*: The same applies, but other way round. The rejected words are rejected for sure, but the still accepted words might be rejected in later iterations.

*D*: A language is decidable, if there *exists* an algorithm, which is computable in finite steps for *every* input whether it is accepted or not. It is also the intersection of SD and CSD, because a decidable language is semi-decidable and co-semi-decidable at the same time.

**Reduction Demystified**

When manufacturing a car, there is no need to reinvent the wheel, we can simply reuse other components produced by other companies to save us a lot of time (and space).

In simple terms, the reduction means reusing the part of an algorithm in another algorithm to reduce the number of problems. Given 2 different problems A and B. We show that we can rewrite A using B internally, also *reduce* A to B, also

**Types of Reduction**

To make it simple, we mean by default reduction *many-to-one* reduction. Many-to-one reduction means that there is no restriction so that the words mapped from A to B using a characteristical function can *overlap* on both sides.

It can be a reduction in terms of computability or complexity, depending on use case:

**Example of Reduction**

For example, finding the maximum can be reduced to sorting problem:

*Side-note*: Finding max is proven to have a lower complexity, which is an example that the reductions might not be useful in all cases. In the following sections, we will see many powerful use-cases of reductions.