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.