Path: utzoo!utgpu!water!watmath!clyde!rutgers!sdcsvax!ucbvax!SCORE.STANFORD.EDU!PAPA
From: PAPA@SCORE.STANFORD.EDU ("C. Papadimitriou")
Newsgroups: comp.theory
Subject: Re: Complexity of optimal addition chains
Message-ID: <8712242357.AA22233@jade.berkeley.edu>
Date: 24 Dec 87 04:35:03 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: TheoryNet List <THEORYNT%NDSUVM1.bitnet@jade.berkeley.edu>,
        "C. Papadimitriou" <PAPA@score.stanford.edu>
Distribution: inet
Organization: The ARPA Internet
Lines: 8


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. ]