Path: utzoo!utgpu!utcsri!arvind
From: arvind@utcsri.UUCP (Arvind Gupta)
Newsgroups: ut.theory
Subject: THEORY NET: Optimal cost addition chains
Message-ID: <5765@utcsri.UUCP>
Date: 6 Jan 88 15:00:48 GMT
Article-I.D.: utcsri.5765
Posted: Wed Jan  6 10:00:48 1988
Distribution: ut
Organization: CSRI, University of Toronto
Lines: 11

*** REPLACE THIS LINE WITH YOUR MESSAGE ***
Date:         8 Dec 1987 15:23:37-EST (Tuesday)
From: "Victor S. Miller" <VICTOR@yktvmz.bitnet>
Subject:      Optimal cost addition chains

Boy am I dense!  After sending out my request I realized that it is
true (almost trivially):  the optimal cost chain is of length < 2*lg n,
so just enumerate them all.  Of course, a more interesting problem arises
if n is written in binary,  does anyone know anything about that ( other
than what's in Knuth v 2)?  In particular, is it NP complete (maybe)?