Log-size assumption

Description

The log-size assumption is an assumption frequently made while computing the computational complexity of various problems. The assumption is as follows: given a group $G$ with an encoding $C$, and a problem described in terms of the encoding, all the input data for the algorithm, as well as the time taken to perform the queries, are polynomial in $n$, where $n$ is the logarithm of the size of the group.

In particular:

• The encoding of each element is polynomial in $n$
• The time taken to perform multiplication and inversion is polynomial in $n$
• If generating sets are involved, the size of the generating set is polynomial in $n$

Thus, when we talk of a polynomial-time algorithm for a problem in the encoding setting, what we mean is an algorithm that is polynomial in the logarithm of the order of the group, subject to the log-size assumption.