計算複雑性理論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/04/28 16:32 UTC 版)
計算複雑性理論（けいさんふくざつせいりろん、英: computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。
- ^ a b c d Sipser, Michael (2006年). “Time Complexity”. Introduction to the Theory of Computation (2nd edition ed.). USA: Thomson Course Technology. ISBN 0-534-95097-3
- ^ Berger, Bonnie A.; Leighton, Terrance (1998年). “Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete.”. Journal of Computational Biology 5 (1): p27-40.、PubMed
- ^ Cook, Stephen (2000年4月) (PDF). The P versus NP Problem. クレイ数学研究所 2006年10月18日閲覧。.
- ^ Jaffe, Arthur M.. “The Millennium Grand Challenge in Mathematics” (PDF). Notices of the AMS 53 (6) 2006年10月18日閲覧。.
- ^ a b Du, Ding-Zhu; Ko, Ker-I (2000年). Theory of Computational Complexity. John Wiley & Sons. ISBN 978-0-471-34506-0
- 1 計算複雑性理論とは
- 2 計算複雑性理論の概要
- 3 決定問題
- 4 計算資源
- 5 イントラクタブル
- 6 外部リンク
計算複雑性理論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/06 16:16 UTC 版)
「In-placeアルゴリズム」の記事における「計算複雑性理論」の解説
計算複雑性理論では、in-place アルゴリズムは空間複雑性が O(1) であるアルゴリズム（DSPACE(1)クラス）を全て含む。このクラスは非常に限定されており、正規言語と等価である。実際、上述の例にあるアルゴリズムはいずれもこのクラスには含まれない。 このため、一般に in-placeアルゴリズムにはLクラスのアルゴリズム（すなわち、O(log n)の追加領域を必要とする問題のクラス）を含める。これは、定義と矛盾しているように見えるが、抽象世界では非常に巨大な入力を考慮する。実際のコンピュータでは、物理メモリ量が限られているためポインタに要する領域は極めて小さいが、サイズ n のリストの添字を表すには一般に O(log n)ビットの領域を必要とする。 この定義によればヒープソートは in-place であるがイントロソートは O((log n)2) の追加領域を必要とするため in-place ではないということになる。 Lクラスのアルゴリズムを in-placeアルゴリズムであると認めると、興味深い洞察が得られる。例えば、無向グラフでの2ノード間の経路が存在するかどうかを決定する in-placeアルゴリズムが存在することになる。通常、この問題は深さ優先探索などでは O(n) の追加領域を必要とする。同様に、2部グラフかどうかの判定問題や2つのグラフが同数の連結成分を持つかどうかという問題などに関しても in-placeアルゴリズムが存在することになる。
※この「計算複雑性理論」の解説は、「In-placeアルゴリズム」の解説の一部です。
「計算複雑性理論」を含む「In-placeアルゴリズム」の記事については、「In-placeアルゴリズム」の概要を参照ください。
計算複雑性理論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/09 06:43 UTC 版)
詳細は「計算複雑性理論」を参照 計算複雑性理論は、問題がコンピュータで解けるかどうかだけでなく、その問題の困難さを扱う。時間計算量と空間計算量という2つの観点がある。時間計算量とは計算にかかるステップ数、空間計算量は計算に必要とされるメモリ量に相当する。 あるアルゴリズムが必要とする時間と空間を分析するため、時間や空間を問題の入力量の関数として表現する。例えば、長い数列から特定の数を見つけ出すという問題は、数列が長くなればなるほど難しくなる。数列に n {\displaystyle n} 個の数があるとき、その数列がソートされていなければ、一個一個の数を確認していくしかない。この場合、この問題の解法の時間計算量は入力量に比例して増大するといえる。 これを単純化するため、O記法が使われる。こうすることで特定のマシンの実装を前提とすることなく、問題の本質的な計算量を扱うことができる。従って、上の例の時間計算量は O ( n ) {\displaystyle O(n)} となる。 計算機科学の中でも最も重要な未解決の問題は、NPと呼ばれる計算複雑性クラスの問題が効率的に解けるかどうかである。詳しくは、P≠NP予想を参照して欲しい。
※この「計算複雑性理論」の解説は、「計算理論」の解説の一部です。
「計算複雑性理論」を含む「計算理論」の記事については、「計算理論」の概要を参照ください。
固有名詞の分類
- 計算複雑性理論のページへのリンク
