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:

1. Computability — Turing Machines, Formal Languages
2. Computability — Classes of Problems, The Art of Reduction [THIS POST]
3. Complexity — Introduction
4. Complexity — Classes and Their Limitations
5. Complexity — Comparison of Different Satisfiability Problems
6. Complexity — We Don’t Know Anything Yet?

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.