Path: utzoo!utgpu!utcsri!arvind
From: arvind@utcsri.UUCP (Arvind Gupta)
Newsgroups: ut.theory
Subject: THEORY NET: Re: Complexity of Optimal Addition chains
Message-ID: <5770@utcsri.UUCP>
Date: 6 Jan 88 15:05:07 GMT
Article-I.D.: utcsri.5770
Posted: Wed Jan  6 10:05:07 1988
Distribution: ut
Organization: CSRI, University of Toronto
Lines: 12

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