Addition-Shift-Sequence問題の計算複雑度について

スポンサーリンク

概要

論文の詳細を見る
本稿では, 整数の列 {n_1, n_2, …, n_m} が与えられた時, これらの整数を1から加減算とシフトによって求める際の演算コストを最小化する問題を定式化し, その計算複雑度を論じる. この問題は従来から研究されているaddition-sequence問題の一般化であり, 複数の定数とある変数における乗算を特定用途向けハードウェアとして実現する場合, 実際上生じるものである. 我々はまず正の整数列を計算する際必要な加算, シフトの総数を最小化する問題の決定問題としてaddition-shift-sequence問題 (ASS) を定義し, ASSがNP完全であることを示す. さらに, 現実的ないくつかの演算コストを考慮した関連問題の複雑度についても議論する.
1998-01-21

著者

関連論文

もっと見る

スポンサーリンク