arvind@utcsri.UUCP (Arvind Gupta) (01/06/88)
*** REPLACE THIS LINE WITH YOUR MESSAGE ***
Date: Wed, 23 Dec 87 22:35:03 CST
From: "C. Papadimitriou" <PAPA@score.stanford.edu>
Subject: Re: Complexity of optimal addition chains
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. ]