Decision problems

---

A decision problem is a problem with a binary answer - yes/no or True/False. That's a bit of a fuzzy definition and decision problems are important in complexity theory. Hence, we'll formalise the definition below. We want to understand the following definition of a decision problem $f$:

$$ f(n) \in \{ \mathrm{T}, \mathrm{F} \} \quad \forall n \in S $$

---

Sets

A set is a collection of objects.

Examples

• The set of chairs in this room.
• The set of boolean values: $\{ \mathrm{T}, \mathrm{F} \}$.
• The set of integers $\mathbb{Z}$.
• The set of prime numbers: $\mathrm{PRIMES} = \{ i | j \nmid i \forall j < i ; i, j \in \mathbb{N}; i, j > 1 \}$.

About sets

• There's not a lot to the definition of set, it's a really basic definition.
• Sets don't have a built-in ordering: $\{ 1, 2, 3 \} = \{ 1, 3, 2\} = \{ 2, 1, 3\} = \ldots$
• Membership cannot be ambiguous.

---

Maps

A map pairs the elements of sets in a specific way.

Tuples