質問: 計算基礎論、クラスpであることの証明 計算基礎論の問題です。 以下の問題が計算量クラスpに含まれることを示せ 行列式の計算 入力:各要素が整数である2×2行列m 出力:|m| 初心者なのでわかりやすく書いていただけると助かります。よろしくお願いします。
回答: アルゴリズムの書き方は多分講義の中で出てると思うんだ. なかったら「プログラム的」に書けばたぶん ok. さしあたり大きく気になるのは 1. 「メモリアクセス数」がそれでいいのか 2. o(・) なのか の 2点かなぁ. 前者については, 例えば m = a * d を計算するときに「それでいけることを示せますか?」ってことね. そこまで維持になって性能を追求しなくても (「多項式」を示すだけなら) いいはず. 後者は, これも講義でどうやってるのか知らないけど厳密にいうと o(・) と o(・) を区別しないとまずい. 細かくいうと 「整数」っていってるけど 0 や負の数があったらどうしよう ってところも問題になるけど... この辺は「どうせ多項式であることを示せばいいや」ってことでかなり雑にやることが多い.