2
$\begingroup$

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?

  • 0
    The wikipedia [page](http://en.wikipedia.org/wiki/Addition-chain_exponentiation#cite_note-0) provides a reference where NP-completeness is claimed proven.2012-09-19

0 Answers 0