# Computability — Classes of Problems, The Art of Reduction

3 min readMar 25, 2022

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.