Log-size assumption

From Groupprops
Jump to: navigation, search


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.