アルゴリズムの線形計画法による基礎づけ
スポンサーリンク
概要
- 論文の詳細を見る
コンピュータサイエンスの基本的問題には,"良い"アルゴリズムが存在することが知られている問題と,"良い"アルゴリズムが知られていない問題とがある.ここで,アルゴリズムの"良い"とは,計算時間や記憶場所の大きさを問題の規模を表す指標の関数で表したときの関数形のことと,一応,見なしておく.例えば,多項式時間の決定性アルゴリズムが存在する問題のクラスをPと表し,多項式時間の非決定性アルゴリズムが存在する問題のクラスをNPと表す.以上は計算の複雑さの理論で周知のことがらである.このような計算の複雑さの理論はTuring機械のモデルで論じられることが多い.一方,クラスPの問題の多くは線形計画問題として記述できる.逆に,線形計画問題として記述できる問題には良いアルゴリズムが存在することが多い(線形計画問題に対するKarmarkarのアルゴリズムとは異なる意味で).そこで,本稿では,整列問題のアルゴリズムを例に,線形計画問題の立場からコンピュータサイエンスの問題を眺め,計算の複雑さに新たな視点を提供することを試みる.
- 1992-02-24
論文 | ランダム
- 今月の注目記事 海上自衛隊初のSH-60J女性機長誕生
- 今月の注目記事 米空母エイブラハム・リンカーン、佐世保に寄港
- 空自・新田原基地航空祭
- Last Summer、Baby…トムキャット・カウントダウン (第2特集・カラーグラフィックス U.S.NAVY最新情報)
- 新田原基地航空祭