Encoding of an IAPS of groups
BEWARE! This term is nonstandard and is being used locally within the wiki. [SHOW MORE]
Let be an IAPS of groups. In other words, for every , there is a group , and there is a map .
An encoding of this IAPS over a binary (or constant-sized) alphabet is the following.
- For every , we specify an encoding of over that alphabet.
- For every , we specify an algorithm that takes as input the code for and , and outputs the code for .
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 is bounded by some constant times the logarithm of the size of .
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 is polynomial in the lengths of the maximum code-words for and .
Encoding of symmetric groups
Further information: Encoding of symmetric groups
Encoding of genereal linear groups
Further information: Encoding of general linear groups