困難な問題の双線形計画問題を用いたモデル化手法

概要

論文の詳細を見る
本論文では, 一般に計算機では解きにくいとされる問題を双線形計画問題(bilinear programming problem)を用いてモデル化する方法を示す.具体的には, 代表的なNP完全問題である「論理式充足可能性問題」の他に, 「大きさKのカバーの存在判定問題」, 「グラフK色彩可能性の判定問題」などのグラフに関する諸問題を双線形計画問題としてモデル化している.また, 本論文では, その結果における, 変数の個数, 制約条件式の個数, 係数行列の非零要素の個数を, 各問題の複雑さを特徴づける静的な量として提案する.これらの静的な量は, どんな計算機械モデルやアルゴリズムにも依存しないため, 問題そのものが持つ不変量と考えられる.また, 双線形計画問題としてモデル化した結果を踏まえて, 困難な問題を相互結合を有する回路問題としてモデル化する方法についても述べる.この回路問題としてのモデルにおける電流制限器の個数と双線形計画問題としてモデルにおける係数行列の非零要素の個数の間に密接な関連があることを示す.
1998-05-22