Date: Fri, 17 Nov 95 13:24:54 CST
From: rusin (Dave Rusin)
To: Andreas.Klappenecker@ira.uka.de
Subject: Re: Q: Complexity of addition chain problem
Newsgroups: sci.math

In article <48ic6b$40n@nz12.rz.uni-karlsruhe.de> you write:
>Is the following problem NP-complete?
>
>Addition chain problem:
>Given a positive number N, find the minimal number of additions necessary to build
>the number N with computations involving the number 1 and additions. 

Just so I understand the question: you are asking for a computation of
the value of  f(N)  for positive integers  N, where  f(N)  is the least
subscript  m  so that  N  lies in the set  S_m; here  S_m consists of
the set of final terms of sequences of length  m,  {a_1, a_2, ..., a_m} with
	1) a_1=1
	2) for each  k<=m  there exists  i <= j < k such that  a_k=a_i+a_j.
(and I assume  (3): the  a_k  are distinct. Indeed, without loss of
generality we may assume  a_i < a_j  when  i<j).	
So we list all possible sequences of a given length to determine the  S_m:
	{1} => S_1 = {1}
	{1,2} => S_2={2}
	{1,2,3} and
	{1,2,4} => S_3={3,4}
	{1,2,3,4}
	{1,2,3,5}
	{1,2,3,6}
	{1,2,4,3}
	{1,2,4,5}
	{1,2,4,6}
	{1,2,4,8} => S_4={3,4,5,6,8} (not 7)
So the function whose computational complexity you wish to study is
	N=   1  2  3  4  5  6  7  8 ...
	f(N)=1  2  3  3  4  4  5  4 ...

Is that the question?
dave