PAPA@SCORE.STANFORD.EDU ("C. Papadimitriou") (12/24/87)
Finding the best addition chain has been conjectured to be NP-complete. As I recall, Ravi Sethi and co-authors have shown that finding the best addition chain for several numbers (to be computed together) is NP-complete. ---CHP [The reference is: Downey, Leong, and Sethi, "Computing sequences with addtion chains," SIAM J. Computing, 10, 3 (August 1981) 638-646. ]