arvind@utcsri.UUCP (Arvind Gupta) (01/06/88)
*** 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)?