「計算的な深さ」について

▼ 「計算的な深さと脳」 で書いた計算的深さの概念はシンプルかつ重要だと思う。
もしそうならこの程度の概念がすでに専門の学者によって発明されていないはずはない。そう思ったのだけど、相変わらず私のアンテナにはかかってこない。もしかしたらまだ存在しないのだろうか。
(中略)
ここで、試論として、「2入力NANDゲートだけで最速な回路構成をした時の計算時間」と定義する。こうすれば大きさNのメモリによる解決はlog N時間かかる事になる。同じ問題を、テーブルで解いてもハードワイアードロジックで解いても同じ程度の時間になるだろう。

ご想像の通り, 既にあります. (並列計算量とか回路計算量の文脈で調べると良いんじゃないかと.)
Complexity Zoo - Qwikiから引っ張ってくると, こんな感じ.

ACi
多項式サイズ/unbounded fan-in/AND, OR, NOT/深さO(log^i(n))/の非一様な回路族で判定可能な問題のクラス
mACi
多項式サイズ/unbounded fan-in/AND, OR/深さO(log^i(n))/の非一様な回路族で判定可能な問題のクラス
NCi
多項式サイズ/2 fan-in/AND, OR, NOT/深さO(log^i(n))の非一様な回路族で判定可能な問題のクラス
mNCi
多項式サイズ/2 fan-in/AND, OR/深さO(log^i(n))の非一様な回路族で判定可能な問題のクラス
TC0
AC0で閾値素子も利用可能なもの

深さで議論する時の基本的なクラスはこんな感じだそうです.

See also: google:計算量 深さから回路計算量 - Wikipedia

あと「P完全問題は並列化しづらいのではないか?」という議論もされている筈.
はてなブックマーク - 計算的な深さと脳の方だと誰も書いてないのね.
微妙に違うかもしれませんが, 東北大の内沢啓さんが閾値素子からなる回路の総エネルギーを制限した場合の計算量について議論しています. 脳の計算モデルにマッチする云々という話だった筈. (参考: DBLP: Kei Uchizawa)

google:並列計算量で2番目にあった. あとで見てみよう.

チューリング機械を並列計算用に拡張した並列乱アクセスTMを提案し,その計算能力がPRAM とほぼ同等であることを証明する. また, 提案した並列乱アクセスTMを用いて並列計算量の時間的階層を示す. t_1(n), t_2(n)≧log nを「時間構成可能な関数」とし, t_2(n)はt_1(n)log s(n) より真に速く増加する関数であるとする. このとき, p(n)プロセッサでs(n)領域の並列乱アクセスTMでO(t_2(n))時間で受理できるが, p(n)プロセッサでs(n)領域のいかなる並列乱アクセスTMでもt_1(n)時間では受理できない言語が存在することを示す.