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!
