Is it hard to find optimal addition chains?
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."