計算複雑度
別名：計算複雑性
【英】computational complexity
計算複雑度とは、計算機が問題を計算するために要する手間を示す尺度のことである。
計算複雑度は、アルゴリズムの性能を評価する基準のひとつとして用いられている。ある問題を解決するために、複数のアルゴリズムを用いることができるとすれば、どのアルゴリズムを選択れば最も効率的に処理できるかを判断するための判断基準の一つとして、計算複雑度を利用することができる。
計算複雑度は、入力サイズの関数として示される。あるアルゴリズムについて、入力サイズがnのとき計算複雑度がnに比例するか、nの多項式で示されない場合、nが極端に大きくなると実用時間内では解けないアルゴリズムとなる。
なお、実用のソフトウェアにおいては、アルゴリズムの>計算複雑度に加えて、プログラムを実行するハードウェアの環境や、プログラム上でのアルゴリズムの実装方法などが複雑に関連する。
計算複雑性理論
(計算複雑性 から転送)
出典: フリー百科事典『ウィキペディア（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）』 (2022/08/11 19:57 UTC 版)
アダマール変換は高速アダマール変換を用いると O ( n log n ) ( n = 2 m ) {\displaystyle O(n\operatorname {log} n)\quad (n=2^{m})} である。
※この「計算複雑性」の解説は、「アダマール変換」の解説の一部です。
「計算複雑性」を含む「アダマール変換」の記事については、「アダマール変換」の概要を参照ください。
計算複雑性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/11/04 08:12 UTC 版)
STRIPS の問題に計画が存在するかどうかの決定問題はPSPACE完全である。様々な制限を加えることで、問題をNP完全にすることができる。
※この「計算複雑性」の解説は、「STRIPS」の解説の一部です。
「計算複雑性」を含む「STRIPS」の記事については、「STRIPS」の概要を参照ください。
計算複雑性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/09/10 08:42 UTC 版)
この問題は、 総当たりまたはバックトラッキングで |V|m の定数倍時間で解くことができる。ここで |V| は使用できる切手の額面の種類の数とする。したがって、封筒の容量 m が定数である場合、多項式時間で解ける問題である。容量 m が任意の場合、問題はNP困難である。
※この「計算複雑性」の解説は、「切手問題」の解説の一部です。
「計算複雑性」を含む「切手問題」の記事については、「切手問題」の概要を参照ください。
計算複雑性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 09:50 UTC 版)
与えられたグラフが単位距離グラフであるか狭義の単位距離グラフであるかを判定する問題はNP-困難である(Schaefer 2013)。 単位距離グラフがハミルトン閉路を持つかどうかは、グラフの頂点がすべて整数座標を持つ場合でもNP-完全である(Itai, Papadimitriou & Szwarcfiter 1982)。
※この「計算複雑性」の解説は、「単位距離グラフ」の解説の一部です。
「計算複雑性」を含む「単位距離グラフ」の記事については、「単位距離グラフ」の概要を参照ください。
計算複雑性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/01 09:24 UTC 版)
計算複雑性理論では、ある数が素数かどうかを判定する問題はPRIMESと表記される。PRIMESがco-NPであることは簡単に示すことができる。なぜなら、その補問題であるCOMPOSITE（ある数が合成数であるかどうかを判定する問題）は、任意の数に対し、問題の数がそれで割り切れるかどうかの確認が多項式時間で行えることよりNPに属するからである。 1975年にVaughan PrattはPRIMESがNPに、また従ってNP ∩ co-NPに属することを示した（Primality certificateを参照）。 Solovay-StrassenとMiller-RabinによるアルゴリズムによりPRIMESはco-RPに属することが判明した。1992年にはAdleman-HuangによるアルゴリズムがZPP = RP ∩ co-RPまで複雑性を下げ、Prattによる結果を更新した。 1983年に発見されたAdleman–Pomerance–Rumelyによる素数判定法によりPRIMESはQPに属することが判明したが、これと上記の結果との関係は分かっていない。 その実際上の扱いやすさや、リーマン予想に基づく多項式時間アルゴリズムの存在、その他の類似の状況証拠により、素数判定は多項式時間でおこなえると長く信じられてきたが、証明はできなかった。AKS素数判定法が最終的にこの長年の問題に終止符を打ち、PRIMESがPに属することを証明した。しかしながら、PRIMESがP-完全かどうかは分かっておらず、NCやLなどのPに含まれるクラスに属するかどうかも分かっていない。PRIMESがAC0に属しないことが証明されている。
※この「計算複雑性」の解説は、「素数判定」の解説の一部です。
「計算複雑性」を含む「素数判定」の記事については、「素数判定」の概要を参照ください。
計算複雑性と同じ種類の言葉
- 計算複雑性のページへのリンク
