計算複雑性理論
(複雑性理論 から転送)
出典: フリー百科事典『ウィキペディア(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 外部リンク
- 複雑性理論のページへのリンク