P=NP問題を理解するためのステップ〜入力サイズ

ソートの計算量も，個数ではなく入力サイズで測るべきでは?

離散対数問題を検討したとき，法pで見ると線形時間になるけれど，実際には入力サイズで測らないといけないので，(準)指数関数になるということから，他のアルゴリズムでも厳格に入力サイズで測らないといけないという主張ですね．
ソートの問題では，入力の値が配列に格納されていて，配列の各要素のサイズが等しいことが前提となっています．このとき，要素数をn，配列の一つの要素のサイズをk，入力長をmとすると，m≒nk となります．ここで「=」ではなく「≒」なのは，厳密に入力サイズを求めるときには，nやkという値(の2進表現)も，入力に含まれるからです．ただし，nが十分に大きければ，これらの値は無視できますnegligible．
バブルソートは， $O(n^2)$ ですね．これは個数に関するオーダです．ここからnを消去して，mのオーダにすればいいのですが… n≒m/k を代入すると，[tex:O*1] となりますが， $(m/k) \log (m/k)$ = 定数1× $m \log m$ -定数2× $m$ なので， $O(m \log m)$ です．
これを一般化すると，次のようになります．すなわち，入力長mと，入力の中で着目する何らかの個数nを考えたとき，mがnに比例するとします．そして，何らかのアルゴリズムがあって，その時間計算量は，nに関する多項式で表現できるものとします．このとき，mについても多項式で表現でき，次数もnと同じになります*2．
配列の各要素のサイズが等しくなく，例えばある要素が入力全体の半分を占めるような入力については，計算時間が変わってきます．というか，見積もりがうんと複雑になります．いい例が思いついたら書くことにします．

2分探索のアルゴリズムは，テューリング機械では O(log n) にならない?

テューリング機械の1ステップの動作で，テープの高々一つ隣しか移動できないとすると，たしかに，真ん中に移動するだけで O(n) かかってしまいます．
配列のある要素を参照するのに要する時間が，要素数に比例しない定数時間であること．これが，2分探索のアルゴリズムが O(log n) となるための前提となっています．
ソートもそうですね．さらっと「i番目とj番目の値を交換する」と書かれていても，この操作に O(n) の時間がかかると，バブルソートの次数が変わってきます．

*1:m/k)^2)] ですが， $(m/k)^2$ = $k^{-2}\cdot m^2$ = 定数× $m^2$ なので，結局， $O(m^2)$ が得られます．次にクイックソートの $O(n \log n)$ だとどうなるでしょうか．同じように n≒m/k を代入すると，[tex:O((m/k) \log (m/k