けいさんのふくざつさとは? わかりやすく解説

Weblio 辞書 > 学問 > OR事典 > けいさんのふくざつさの意味・解説 

計算の複雑さ

読み方:けいさんのふくざつさ
【英】:computational complexity

概要

「計算の複雑さ」とは, その計算が必要とする計算資源の量を, 入力長さ対す関数としてとらえるものである. 計算モデルとしては, チューリング機械RAMモデル使われ, 資源として計算時間計算必要な領域評価される. 一般に入力によって計算必要な資源変化するので, 入力長さに関して最悪場合考える. 微妙な議論をしている場合以外は, 関数多項式程度の差は無視する場合が多い.

詳説

 「計算の複雑さ」とは,その計算が必要とする資源の量を,入力長さ対す関数としてとらえるものである計算モデルとしては,チューリングマシンモデルが使われ資源として計算時間計算必要な領域評価される入力によって計算必要な資源変化するので,通常入力長さに関して最悪場合考える.微妙な議論をしている場合以外は,関数多項式程度の差は無視する場合が多い.こうした観点から言えば現在世の中で利用されているフォン・ノイマン型の計算機はすべてチューリングマシンモデルで模倣することができる.また現実的に手に負え問題とは,多項式時間アルゴリズム解ける問題だけと考えられている.

 計算の複雑さの理論でもっとも有名な未解決問題は,{\rm P}\neq {\rm NP}\, 予想である.これはクラス{\rm NP}\, 属す問題がすべて多項式時間解けるかどうか,という問題対す予想である.NP困難な問題数多く知られており,その中には実用上,重要な問題含まれている (文献 [1] に詳細なリストがある).多く研究者は,NP困難問題多項式時間では解くことはできないであろう,と予想している.つまりこうした計算の複雑さの理論枠組みによれば,ある問題NP困難であることを示す,ということは,すなわちその問題が「手に負えない問題であることを示したということであった

 しかし一方ではこうした従来枠組みによって「手に負えない」とされた問題を,なんとかして現実的な観点から解決できないか,というアプローチいくつか行われてきた.代表的なものとしては,確率的なアルゴリズムと,近似アルゴリズムとがあげられる

 確率的なアルゴリズムとは,計算機基本的な機能としてコイントス付加するアプローチである.コイントス許したチューリングマシンモデル (確率チューリングマシンモデル) を導入し正解出力する確率によって問題クラス定義する例え一方向エラー許した多項式時間確率チューリングマシンによって判定できる問題クラスR属する.与えられた数が合成数かどうか判定する問題が,クラスR属することはよく知られている.こうしたアルゴリズムについては,文献 [6] が詳しい.

 近似アルゴリズムとは,厳密なではなく近似解得られればよい,というスタンスに立つものである近似解とは,通常厳密な解に対す相対誤差正定数で抑えられるものを言う場合が多い (問題によっては相対誤差でなかったり,正定ではなく関数であったりする場合もある).相対誤差正定\epsilon\, 抑えられる解を\epsilon\, 近似の解と呼ぶ.近似アルゴリズムでは正定\epsilon\, に対して入力長さ」と「1/\epsilon\, 」の多項式時間\epsilon\, 近似の解を求めることができるかどうか,という基準で「手に負えない問題であるかどうか決める.同じNP困難問題であってもこうした観点からは違った性質をもつものがあることがわかっている. つまりNP困難問題であっても与えられ任意の正定\epsilon\, に対して上記の意味での多項式時間\epsilon\, 近似の解を求めることができるものがあり,一方で({\rm P}\neq {\rm NP}\, 仮定のもとでは)\, 多項式時間\epsilon\, 近似の解を求めることのできるような\epsilon\, 大きさ限界がある問題知られている.後者問題属すクラス一つとしてクラスMAX SNP知られている.つまりMAX SNP困難な問題は,厳密解だけではなく,よい近似解求めることですら「手に負えない問題である,ということになる.ここで注意すべき点は,こうした意味で「手に負えない問題であってもある程度近似アルゴリズム知られているものがある,ということである.つまりいくらでもよい近似率を達成するのは困難ではあるが,特定の近似率を実現するであればなんとかなる問題もある.しかしこうした問題近似率をどこまで小さくできるか,という問題一般には非常に難しい.こうした問題最近の結果については,文献[3][8]が詳しい.

 計算の複雑さの理論では,こうした「手に負えかどうか」という観点とは別の切口から問題複雑さ研究する分野もある.例えば「与えられ問題並列効率よく解くことができるかどうか」という観点実用上,重要な意味を持つ.ある問題に対して並列化効果的かどうかは,その問題がどの程度並列性」を有しているかによる.並列性有する問題クラス一つクラスNCである.このクラス属す問題は,プロセッサ増やせば,その分だけ効率よく問題を解くことができる.多項式時間アルゴリズムを持つ問題中には,このクラス属さないであろう,と強く予想されている問題もある.こうした問題プロセッサ数を増やして計算高速化には限界がある.こうした並列計算に関する問題については,文献 [2] のリストが詳しい.

 なお本項全般については,文献 [5, 7] が詳しい.文献 [4] は非常に幅広い話題網羅し著名なハンドブックである.




参考文献

[1] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness}, Freeman, San Francisco,1979.

[2] R. Greenlaw, H. J. Hoover and W. L. Ruzzo, Limits to Parallel Computation, Oxford University Press, 1995.

[3] D. S. Hochbaum (eds.) Approximation Algorithms for NP-hard Problems, PWS Publishing Company, 1995.

[4] J. van Leeuwen (eds.) Handbook of Theoretical Computer Science, Elsevier Science Publishers, 1990.

[5] 守屋悦朗,『チューリングマシン計算量理論』, 培風館, 1997.

[6] R. Motwani and P. Raghavan Randomized Algorithms, Cabbridge, 1995.

[7] C.H. Papadimitriou Computational Complexity, Addison-Wesley Publishing Company, 1994.

[8] V. V. Vazirani, Approximation Algorithms, Springer, 2001. 浅野孝夫訳, 『近似アルゴリズム』, シュプリンガー・フェアラーク, 2002.




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「けいさんのふくざつさ」の関連用語

けいさんのふくざつさのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



けいさんのふくざつさのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2025 (社)日本オペレーションズ・リサーチ学会 All rights reserved.

©2025 GRAS Group, Inc.RSS