計算複雑性理論
出典: フリー百科事典『ウィキペディア（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 外部リンク
固有名詞の分類
このページでは「ウィキペディア」から計算複雑性理論を検索した結果を表示しています。
Weblioに収録されているすべての辞書から計算複雑性理論を検索する場合は、下記のリンクをクリックしてください。
全ての辞書から計算複雑性理論を検索
Weblioに収録されているすべての辞書から計算複雑性理論を検索する場合は、下記のリンクをクリックしてください。
全ての辞書から計算複雑性理論を検索 - 計算複雑性理論のページへのリンク
