Computing the length of the shortest addition chain that contains a given number can be done by dynamic programming for small numbers, but it is not known whether it can be done in polynomial time measured as a function of the length of the binary representation of .