計算複雑性理論
computational complexity theory
計算量理論
どの程度の計算コストで計算できるか
この「計算コスト」は通常は
チューリングマシン
の動作のステップ数で測る
計算複雑性理論で扱う計算問題の多くは
決定問題
である
ブラムの公理
https://ja.wikipedia.org/wiki/ブラムの公理
ブラムの加速定理
ギャップ定理
算術的階層
関連
複雑性クラス
関数問題
https://ja.wikipedia.org/wiki/関数問題
チューリング次数
参考
https://ja.wikipedia.org/wiki/計算複雑性理論