# 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:

- Computability — Turing Machines, Formal Languages
- Computability — Classes of Problems, The Art of Reduction
**[THIS POST]** - Complexity — Introduction
- Complexity — Classes and Their Limitations
- Complexity — Comparison of Different Satisfiability Problems
- 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.