Is it hard to find optimal addition chains? An addition chain is a sequence of positive integers $(x_1, x_2, \dots, x_n)$ where $x_1 = 1$ and  each index $i\ge 2$, we have $x_i = x_j + x_k$ for some indices $1\le j,k &lt; i$.  The length of the addition chain is $n$; the target of the addition chain is $x_n$.

What is known about the complexity of the following problem: Given an integer $N$, what is the length of the shortest addition chain whose target is $N$?  Is it NP-hard?

Wikipedia points to a 1981 paper by Downey, Leong, and Sethi that proves the following related problem is NP-hard: Given a set of integers what is the minimum length of an addition chain that includes the entire set?  Several authors apparently claim that this paper proves the single-target problem is NP-hard, but it doesn't.
The problem is mentioned as being open in Eric Lehman's PhD thesis "Approximation algorithms for grammar-based data compression" in 2002. From p35 of the thesis:

"Nevertheless, an exact solution to the addition chain problem remains strangely elusive. The M-ary method runs in time polylog(n) and gives a 1 + o(1) approximation. However, even if exponentially more time is allowed, poly(n), no exact algorithm is known."