アルゴリズムの線形計画法による基礎づけ
スポンサーリンク
概要
- 論文の詳細を見る
コンピュータサイエンスの基本的問題には,"良い"アルゴリズムが存在することが知られている問題と,"良い"アルゴリズムが知られていない問題とがある.ここで,アルゴリズムの"良い"とは,計算時間や記憶場所の大きさを問題の規模を表す指標の関数で表したときの関数形のことと,一応,見なしておく.例えば,多項式時間の決定性アルゴリズムが存在する問題のクラスをPと表し,多項式時間の非決定性アルゴリズムが存在する問題のクラスをNPと表す.以上は計算の複雑さの理論で周知のことがらである.このような計算の複雑さの理論はTuring機械のモデルで論じられることが多い.一方,クラスPの問題の多くは線形計画問題として記述できる.逆に,線形計画問題として記述できる問題には良いアルゴリズムが存在することが多い(線形計画問題に対するKarmarkarのアルゴリズムとは異なる意味で).そこで,本稿では,整列問題のアルゴリズムを例に,線形計画問題の立場からコンピュータサイエンスの問題を眺め,計算の複雑さに新たな視点を提供することを試みる.
- 1992-02-24
論文 | ランダム
- 異文化接触の実態と際立った異文化接触
- 照応形Do So, Do Itに関わるOutbound Anaphoraの一考察
- Stimulation of Annexin A5 Expression by Gonadotropin Releasing Hormone (GnRH) in the Leydig Cells of Rats
- 硬質被膜内の応力解析による被膜損傷メカニズムの推定 (特集 材料分析・評価技術)
- 硬質被膜内の応力解析による被膜損傷メカニズムの推定