20
$\begingroup$

An addition chain is a sequence of positive integers $(x_1, x_2, \dots, x_n)$ where $x_1 = 1$ and each index $i\ge 2$, we have $x_i = x_j + x_k$ for some indices $1\le j,k < i$. The length of the addition chain is $n$; the target of the addition chain is $x_n$.

What is known about the complexity of the following problem: Given an integer $N$, what is the length of the shortest addition chain whose target is $N$? Is it NP-hard?

Wikipedia points to a 1981 paper by Downey, Leong, and Sethi that proves the following related problem is NP-hard: Given a set of integers what is the minimum length of an addition chain that includes the entire set? Several authors apparently claim that this paper proves the single-target problem is NP-hard, but it doesn't.

$\endgroup$
  • 2
    $\begingroup$ two questions: $N$ is given in binary form I assume, and can the $j$ and $k$ be identical (if so, then there's always a sequence of length log n via binary expansion) $\endgroup$ – Suresh Venkat Sep 3 '10 at 17:11
  • $\begingroup$ Let's assume $N$ is given in binary, although I don't know of a poly-time algorithm even when $N$ is unary. And yes, adding to yourself is allowed — in fact, required to get off the ground. The shortest chain for 128 is (1, 2, 4, 8, 16, 32, 64, 128). $\endgroup$ – Jeffε Sep 4 '10 at 2:23
11
$\begingroup$

The problem is mentioned as being open in Eric Lehman's PhD thesis "Approximation algorithms for grammar-based data compression" in 2002. From p35 of the thesis:

"Nevertheless, an exact solution to the addition chain problem remains strangely elusive. The M-ary method runs in time polylog(n) and gives a 1 + o(1) approximation. However, even if exponentially more time is allowed, poly(n), no exact algorithm is known."

$\endgroup$
2
$\begingroup$

And on the main paper of Lehman's thesis, there is a good overview of the problem (section V B) with references.

$\endgroup$
1
$\begingroup$

I would like to document some partial progress - seemingly promising so far - towards a polynomial time algorithm. UPDATE: Added some details to account for a glitch pointed out by @David (thanks!).

The approach is to reduce this to an instance of MIN-ONES EVEN-3 CSPs (MOEC), which happens to be a polynomial time solvable problem. The proof of the reduction is a bit fuzzy, but I am hopeful that it exists!

An instance of MOEC is a family of $3$-sized subsets of an universe of variables, and an integer $k$. The question is whether there is a satisfying assignment of weight at most $k$, where an assignment is a function from the universe to $\{0,1\}$, the weight of an assignment is the number of variables that it assigns one, and an assignment is satisfying if, for every subset of variables $\{x,y,z\}$, the assignment (say $f$) has the property that:

$f(x) + f(y) + f(z) = 0 (mod ~~2)$.

You could visualize this as 3-SAT with a different notion of satisfiability - pick none or pick two. I'll be a bit lax about the instance of MOEC in that I will allow for, apart from the usual $3$-subsets, implications, disjunctions of length two, and the constraint $(x = 1)$. I believe these simple additions will keep the problem polynomial time.

Let's say we're reducing the addition chain problem for the number $n$. The variable set for this reduction is the following:

For every $1 \leq i \leq n$, the variable $N_i$. I will re-write the variable $N_n$ as $N$. For every pair $i,j$ such that $1 \leq i,j \leq k$, introduce variables $P_{ij}$ and $Q_{ij}$.

Introduce the following subsets, for every $i,j,k$ such that $k = i+j$:

$\{P_{ij}, Q_{ij}, N_k \}$

and the following implications:

$P_{ij} \Rightarrow N_i$ and $P_{ij} \Rightarrow N_j$

and the following constraints:

$(N_1 = 1), (N = 1)$.

Finally, we need to add constraints that ensure that at least one of the $P$-variables are picked when a "corresponding" $N$-variable (forgive the abuse of notation) is assigned one. This can be done by adding the usual OR constraint over all $P_{ij}$ such that $i + j$ sum to the $N$-variable in question. We have to, however, find a way of re-encoding this in MOEC-framework.

So let me outline a general way of saying, given a set of variables:

$(X, l_1, l_2, \ldots, l_t)$,

how the constraint "if an assignment is satisfying and sets $X$ to one, then exactly one of the $l_i$'s must be set to one by the assignment", can be encoded with the MOEC syntax. Note that this suffices for our requirements, we simply introduce the constraints:

$(N_k, \{ P_{ij} ~|~ i + j = k \})$.

The encoding is done as follows. Let $T_X$ be the rooted complete binary tree on $t$ leaves. Introduce a new variable $T_{di}$ for all $1 \leq d \leq \log t$ and $1 \leq i \leq {\cal L}(d)$, where ${\cal L}(d)$ denotes the number of nodes of $T_X$ at depth $d$.

For every node $T_{di}$, if $p$ and $q$ be its children in the tree, introduce the EVEN-3 constraint:

$\{T_{di},p,q\}$

This means that if a variable corresponding to a node is set to true, then exactly one of its children must be set to true as well. Now add the implications:

$(X \Rightarrow T_{11})$ and $(d_{\log t,j}) \Rightarrow l_j$ (comma for clarity).

This combination of EVEN-3 constraints and implications is equivalent to constraint that we wished to encode.

Intuitively, what's happening is that the last two constraints trigger exactly the reactions required to build an addition chain. In particular, let us look at the $N_i$'s that are assigned one by a satisfying assignment - the claim is that they will form an addition chain for $N$: since the assignment is forced to set $N$ to one, there must be at least one $P_{ij}$ that was set to one, and the implications force $N_i$ and $N_j$ to be assigned one, and this goes all the way down (I am sure this can be formalized with induction, although I haven't worked out that level of detail yet). Note that a satsifying assignment that is optimal in the number of ones assigned will not set $P_{ij}$ true for two pairs $(r,s)$ and $(r',s')$, for the reason that the $P$-variables come with the additional baggage of the implications, and the $Q$-variables don't (they are there to ensure EVEN-3 satisfiability - on a clause where $N_i$ is true and $P_{ij}$ is not true, we still need to pick something to satisfy that clause, and for reasons that are easy to see, this cannot be one universal variable across clauses).

So I believe an addition chain corresponds to a satisfying assignment and vice-versa. Let me describe one part of this somewhat formally: given an addition chain, we construct an assignment $f$ that is satisfying. To begin with, $f$ sets all $N_i$'s that feature in the chain to one, and the other $N_i$'s to zero. Further, if $k$ features in the addition chain, then for each $N_k$, let $i_k,j_k$ be the elements in the chain such that $i_k + j_k = j$. Then $f$ sets $P_{i_k j_k}$ to one (and $Q_{i_k j_k}$ to zero), and all $(i,j)$ such that $i \neq i_k$ and $j \neq j_k$ and $i+j = k$, $f$ sets $Q_{ij}$ to one (and $P_{ij}$ to zero). For all $k$ that don't feature in the addition chain, for all $i,j$ such that $i+j = k$, set all $Q_{ij}$ and $P_{ij}$ to zero (notice that consistency follows from the fact that two numbers add up in only one way). Every clause involving a $N_i$ in the chain is satisfied because either a P-variable or Q-variable corresponding to it was set to one (and notice that exactly one of them are set to one for any pair $(i,j)$). For every other clause, everything is set to zero. That the implications hold is easy to check.

The part that is unclear is the following: because for every element $t$ chosen in the addition chain, the assignment incurs a weight of $t$ (because of all the $Q$-variables being set to one). So there is a possibility that a longer additional chain would correspond to a cheaper assignment, but I am quite sure this doesn't happen because of a proof along the following lines: consider an optimal addition chain and suppose there is a longer one that has a smaller-weight satisfying assignment corresponding to it. Clearly, the elements of the longer chain exclude at least one from the shorter one - let that element be $x$. I wish to say that the cost incurred with $x$ is incurred in the longer chain anyway, and the remaining compares favorably. However, I have to write this down carefully, and I might just be seeing things from post-midnight syndrome!

$\endgroup$
  • 1
    $\begingroup$ If this does work, it seems that it would still be exponential time (when N is expressed in binary) because the number of variables is proportional to N^2 rather than polylog(N). $\endgroup$ – David Eppstein Sep 4 '10 at 20:12
  • $\begingroup$ Ah yes, I should have emphasized that. I was thinking of $N$ in unary following @JeffE's remark that even that is not clear. I do plan to think about cutting down the instance size further, but at the moment am more keen on ensuring this is alright. If it is, I think there is room aplenty for improvement. Incidentally, would you find the approach promising? $\endgroup$ – Neeldhara Sep 4 '10 at 20:20
  • $\begingroup$ I don't see how the constraints you describe force a solution to be valid. What stops you from setting P_ij=0 and Q_ij=1 for all i+j=n, and P_ij=Q_ij=0 for all other i,j? $\endgroup$ – David Eppstein Sep 4 '10 at 23:11
  • $\begingroup$ Thanks for wading through that! And yes, you are quite right; I meant to add a constraint that said any of the $N_i$'s implies one of the relevant $P_{ij}$'s, but realized it blows up the complexity of the instance into the Hitting Set domain, and while I meant to fix it, I think I forgot about it instead. I have updated the answer with a possible fix, it's just a slightly tedious (but simple) construction. $\endgroup$ – Neeldhara Sep 5 '10 at 4:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.