「計算量理論 演習問題」の解答メモです。自分の勉強用につくったものなので、内容に保証はありません。 問2.1 とする時、定義より、多項式 と 時間限定の機械 M が存在する。十分大きな について となるので、この を用いて、従って、一方、任意の について…