計算量理論入門 ―複雑さをとらえる―50 計算能力の階層 令和4年5月13日 河村 現代の数学と数理解析 50 計算量理論 「どれほど計算し難いか」という尺度で 複雑さを測る Complexity Theory (Computational) 1 50 １．問題と機械 50 1 5 6 3 4 2 7 × ○ × ○ × ○ ○ ここでは 与えられた正整数（十進法で書く）が素数か答えよ （入力は文字列で表される） 与えられた文字列に「aba」が現れるか答えよ 0 1 … 9 からなる文字列 a と b からなる と考えることにする 例えば 問題 PRIME 問題 ABA 計算して問題を解くことの難しさを論じたいので…… まず 問題とは？ 各入力に対して 答が○か×か定めたもの 答 入力 2 50 ここでは 与えられた正整数（十進法で書く）が素数か答えよ （入力は文字列で表される） 0 1 … 9 からなる文字列 と考えること
