アルゴリズムの線形計画法による基礎づけ
スポンサーリンク
概要
- 論文の詳細を見る
コンピュータサイエンスの基本的問題には,"良い"アルゴリズムが存在することが知られている問題と,"良い"アルゴリズムが知られていない問題とがある.ここで,アルゴリズムの"良い"とは,計算時間や記憶場所の大きさを問題の規模を表す指標の関数で表したときの関数形のことと,一応,見なしておく.例えば,多項式時間の決定性アルゴリズムが存在する問題のクラスをPと表し,多項式時間の非決定性アルゴリズムが存在する問題のクラスをNPと表す.以上は計算の複雑さの理論で周知のことがらである.このような計算の複雑さの理論はTuring機械のモデルで論じられることが多い.一方,クラスPの問題の多くは線形計画問題として記述できる.逆に,線形計画問題として記述できる問題には良いアルゴリズムが存在することが多い(線形計画問題に対するKarmarkarのアルゴリズムとは異なる意味で).そこで,本稿では,整列問題のアルゴリズムを例に,線形計画問題の立場からコンピュータサイエンスの問題を眺め,計算の複雑さに新たな視点を提供することを試みる.
- 1992-02-24
論文 | ランダム
- Burkholderia pseudomalleiが分離された2症例の経験
- Nocardia farcinica による脳ノカルジア症の1症例
- 肺高血圧を伴う先天性心疾患の手術時におけるPhenoxybenzamineの応用(肺血管抵抗に及ぼす効果)
- 当院における血中分離菌の検討 : 開院後約7年間の集計成績をもとに
- 特別座談会 廃棄物処理法における排出責任を負う事業者は誰か?(後編)さまざまなケースについて考える