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 with an encoding , 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 , where is the logarithm of the size of the group.
- The encoding of each element is polynomial in
- The time taken to perform multiplication and inversion is polynomial in
- If generating sets are involved, the size of the generating set is polynomial in
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.