Encoding of an IAPS of groups

BEWARE! This term is nonstandard and is being used locally within the wiki. [SHOW MORE]
For its use outside the wiki, please define the term when using it. If you are aware of an equivalent standard term, please leave a comment on the talk page
VIEW: Definitions built on this | Facts about this: (facts closely related to Encoding of an IAPS of groups, all facts related to Encoding of an IAPS of groups) |Survey articles about this | Survey articles about definitions built on this
VIEW RELATED: Analogues of this | Variations of this | Opposites of this |
Learn more about terminology local to the wiki | view a complete list of such terminology

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}$ .