# Encoding of an IAPS of groups

BEWARE! This term is nonstandard and is being used locally within the wiki. [SHOW MORE]

## Definition

Let $(G,\Phi)$ be an IAPS of groups. In other words, for every $n$, there is a group $G_n$, and there is a map $\Phi_{m,n}: G _n \times G_n \to G_{m+n}$.

An encoding of this IAPS over a binary (or constant-sized) alphabet is the following.

• For every $G_n$, we specify an encoding of $G_n$ over that alphabet.
• For every $m,n$, we specify an algorithm that takes as input the code for $g \in G_m$ and $h \in G_n$, and outputs the code for $\Phi_{m,n}(g,h)$.

## Properties

### Dense encoding of an IAPS of groups

Further information: dense encoding of an IAPS of groups

An encoding of an IAPS of groups is said to be dense if the maximum possible length of a code-word for $G_n$ is bounded by some constant times the logarithm of the size of $G_n$.

### Polynomial-time encoding of an IAPS of groups

Further information: polynomial-time encoding of an IAPS of groups

An encoding of an IAPS of groups is said to be polynomial-time if:

• The time taken for all the operations (outputting the identity element, computing the product, computing the inverse, testing for membership) is polynomial in the length of the maximum code-word.
• The time taken for $\Phi_{m,n}$ is polynomial in the lengths of the maximum code-words for $G_m$ and $G_n$.

## Examples

### Encoding of symmetric groups

Further information: Encoding of symmetric groups

### Encoding of genereal linear groups

Further information: Encoding of general linear groups