Lesson 4

Another example. Let \(S \subseteq \mathbb{Z}\). In the problem \(\mathcal{P}_{S}\), given a number \(n \in \mathbb{Z}\), the task is to return 1 if \(n \in S\), and 0 otherwise. For example, if \(S=\mathbb{P}\), the problem consists of checking primality, and for \(S=\{x \in \mathbb{Z}\colon \text{\(x\) is even}\}\) — in checking whether the number is even. Again, it is clear that there exists a set \(S\) such that no program exists for the problem \(\mathcal{P}_{S}\), but again, this does not particularly hinder us in practice.