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
In [ ]: