Indexverzameling

In de wiskunde kunnen de elementen van een verzameling A worden geïndexeerd of gelabeled met behulp van een verzameling J, die om die reden een indexverzameling wordt genoemd. Het indexeren bestaat uit een surjectieve functie van J op A en de geïndexeerde collectie wordt typisch een geïndexeerde familie genoemd, wat vaak wordt genoteerd als (A_j)_j∈J.

In de complexiteitstheorie en cryptografie is een indexverzameling een verzameling, waarvoor een algoritme I bestaat, dat deze verzameling efficiënt kan doorlopen en bevragen; dat wil zeggen dat op basis van een korte input (lengte n) de indexverzameling I een veel langer (veelvoud van lengte n) element uit de verzameling kan selecteren en teruggeven.

Voorbeelden

• Een opsomming van een verzameling S geeft een indexverzameling $J \sub \mathbb{N}$, waar $f:J \rarr \mathbb{N}$ de verbijzonderde opsomming van S is.
• Enige oneindig telbare verzameling kan worden geïndexeerd door $\mathbb{N}$.
• Voor $r \in \mathbb{R}$, is de indicatorfunctie op r de functie $\mathbf{1}_r\colon \mathbb{R} \rarr \mathbb{R}$ gegeven door

$\mathbf{1}_r (x) := \begin{cases} 0, & \mbox{if } x \ne r \\ 1, & \mbox{if } x = r. \end{cases}$

De verzameling van alle $\mathbf{1}_r$ functies is een overaftelbare verzameling geïndexeerd door $\mathbb{R}$.

Zie ook

• Index