計算問題と計算量・複雑性

ウィキペディア小見出し辞書

計算問題と計算量・複雑性

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 20:32 UTC 版)

「計算複雑性理論」の記事における「計算問題と計算量・複雑性」の解説

計算複雑性理論で扱う問題とは、ある一連の問いの集合があり、各問いは有限長の文字列で表され、与えられた問いに対して解を求めて出力する計算問題である。例えば、FACTORIZE問題とは「二進数で書かれた1つの整数について、その素因数を全部求めて返す」という問題である。問題に属する個別の問いをインスタンスと呼ぶ。例えば、「15 の素因数を求めよ」は FACTORIZE 問題のインスタンスである。 アルゴリズムの計算量（けいさんりょう）とは、計算機がそのアルゴリズムの実行に要する計算資源の量をいい、アルゴリズムのスケーラビリティを示す。形式的には計算機をチューリング機械やランダムアクセス機械（random access machine）などの計算モデルとして定式化したうえで、アルゴリズムの使用する資源の量を入力データ長などに対する関数として表す。計算モデルの瑣末な詳細に影響を受けないよう、計算量はその漸近的な挙動のみに注目し、定数倍を無視するO記法で書き表すことが多い。計算モデルとしては、チューリング機械や論理回路などがある。計算資源の量としては、チューリング機械における時間計算量（動作ステップ数）や空間計算量（テープ長）、また論理回路における素子数や深さなどがある。 時間計算量は、あるアルゴリズムを使ったときに問題のインスタンスを解くのに要するステップ数を意味し、入力データの長さ（ビット数などで表現できる）の関数として表される。シンプルな例として、ある問題に対する解法が nビットの入力に対して、ある計算モデルで n2 ステップで動作する場合、時間計算量は n2 であるが、他のほとんどの計算モデルでも、時間計算量は漸近的には定数倍の違いしかなく、O記法を使えば計算モデルによらず問題の時間計算量をO(n2) と表せる。計算を芝生を刈る作業にたとえれば、その時間計算量は線型であり、芝生の面積が2倍になれば時間も2倍かかる。この面積が2倍になれば時間も2倍になるという関係は、芝刈機の速度には関係しない。しかし、辞書を二分探索する場合の時間計算量は対数時間であり、辞書の厚さが2倍になっても、二分探索のステップが1増加するだけである。 空間計算量は、同様の概念であり、アルゴリズムが必要とする記憶容量を意味する。例えば、紙とペンを使って計算を行う際に要する紙の枚数に相当する。空間計算量にもO記法が使われる。 計算モデルによっては、これらとは異なる計算量が使われることもあり、例えば回路計算量がある。これは問題の解法をブール論理による論理回路ゲートに置き換え、その回路の規模で計算量を現すものである。これは集積回路の設計などで利用される。 計算問題の複雑性（または計算量）とは、それがどの計算モデルにおいて、どれほどの計算量のアルゴリズムによって解けるかで測られる。直感的には、問題の計算量は、最も効率のよいアルゴリズムを使ったときに問題のインスタンスを解くのに要する計算量だと考えるのが自然である。しかし、最良のアルゴリズムであることを示すのは通常困難で、多くの場合、O記法を用いて「ある時間以下で計算できる」ことを示すことになる。そのため、複雑性クラスを導入し、クラス間の相互関係を示すことで、計算問題の複雑性を明らかにする。