いけがみです。

僕が申し訳ないと思ったのは、
 村井さんは最小長が知りたいのであって、
 最小の長さの連鎖の構成が必要ではない(のだろう)
という推測ゆえです。

というのは、連鎖を構成できずとも、
最小の長さを求めるアルゴリズムは存在するかもしれませんから。
(以下に書いた conjecture (*) のせいで、
 最小の長さを求める"効率がよい"アルゴリズムは存在しないでしょうけれど)

ちょっと古いですが、1997 年に D. M. Gordon が書いたサーベイを
みつけました。
http://citeseer.nj.nec.com/gordon97survey.html

-- 以下 余談 --

NP-hard は decision problem について定義されます。
(yes または no のみを答とする問題)

加法連鎖に関しては、
 非負整数 L をあたえたとき、 L よりも短い連鎖は存在するか? (yes or no)
という問題が NP-hard だ(ろう)ということです。
# 僕が事実を確かめていないので、憶測ですみません。

もしも上の決定問題が NP-hard ならば、(たぶんそうですが)
(P \neq NP conjecture を仮定すると)、
最小値を求める問題や最小長の連鎖を求める問題は
一般的に難しい問題であると結論できます。(*)
(仮に、最小値や最小長の連鎖を多項式時間で構成できたら、
上の決定問題が多項式時間で解けることになるので P=NP となる)

--
# いつも言葉が足りないか多すぎて失敗してしまう。