計算基礎論、クラスPであることの証明

計算基礎論の問題です。

以下の問題が計算量クラスPに含まれることを示せ
　行列式の計算
　入力:各要素が整数である2×2行列M
出力:|M|

初心者なのでわかりやすく書いていただけると助かります。よろしくお願いします。

質問者からの補足コメント

• 定義と計算はできますがアルゴリズムのメモリアクセス数の計算に自信がありません。アルゴリズムの書き方がこれであってるのかも自信がないです。
  もしよろしければご確認お願いします。
  
  int M[2][2]={{a,b},{c,d}}
  det(a,b,c,d){
  int m,n
  m=a＊d
  n=b＊c
  return m-n
  }
  入力長n=o(logabcd)
  メモリアクセス数が、o(loga+logd)+o(logb+logc)+o(logm+logn)=o(2logabcd)=o(n)
  よってこの問題はクラスPである。
  
  こんな感じで解いてみました。

  No.1の回答に寄せられた補足コメントです。 補足日時：2020/01/16 00:32

No.1 回答者： Tacosan 回答日時： 2020/01/16 00:17

具体的にはなにがわからない? 「P」の定義はわかるよね? 行列式は計算できるよね?

No.2 ベストアンサー 回答者： Tacosan 回答日時： 2020/01/16 01:43

アルゴリズムの書き方は多分講義の中で出てると思うんだ. なかったら「プログラム的」に書けばたぶん OK.

さしあたり大きく気になるのは
1. 「メモリアクセス数」がそれでいいのか
2. o(・) なのか
の 2点かなぁ.

前者については, 例えば m = a * d を計算するときに「それでいけることを示せますか?」ってことね. そこまで維持になって性能を追求しなくても (「多項式」を示すだけなら) いいはず.

後者は, これも講義でどうやってるのか知らないけど厳密にいうと o(・) と O(・) を区別しないとまずい.

細かくいうと
「整数」っていってるけど 0 や負の数があったらどうしよう
ってところも問題になるけど... この辺は「どうせ多項式であることを示せばいいや」ってことでかなり雑にやることが多い.

この回答へのお礼

昨日解決しました。
何度も回答いただきありがとうございました。

お礼日時：2020/01/17 16:46