どの程度の計算コストで計算できるか

この「計算コスト」は通常はチューリングマシンの動作のステップ数で測る

計算複雑性理論で扱う計算問題の多くは決定問題である

関連

参考