Computability — Classes of Problems, The Art of Reduction

Yamac Eren Ay
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:

  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.