Encoding of an IAPS of groups

From Groupprops
Jump to: navigation, search
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