# Finding the minimum length of an addition chain

It is known that for every positive integer $n$ there exists one or more optimal addition chains of minimum length. It is rumored that finding the length of the optimal chain is NP-hard, and the related Wikipedia article only provides methods to calculate relatively short chains but not the optimal chain.

1- What methods exist that can find the optimal addition chain for a given $n$?

2- How fast are these methods and how well do they scale with $n$?

3- Do methods exist that will only calculate the length of the optimal chain and could they be faster than ordinary methods?

4- Could a function that relates to addition chains be recursive?

-
I seem to remember that there is discussion of this topic in Volume 2 of Knuth The Art of Computer Programming, in connection with finding the optimal sequence of multiplications for calculating $x^n$ for given integer $n$. –  MJD Sep 19 '12 at 14:23
The wikipedia page provides a reference where NP-completeness is claimed proven. –  Sasha Sep 19 '12 at 16:32