計算上の複雑さの中で時間と空間を越えている他のリソース

Question

一般に、計算上の複雑さでは、時間と空間の複雑さについて話します。つまり、何らかの問題を解決するために必要な時間やスペースがどれだけあるかを考えます。

コンピューティングの複雑さを論じるためのリファレンスを使用できる別の種類のリソース（時間と空間を超えて）があるかどうかを知りたいと思います。

Answer 1

外部メモリ（https://www.ittc.ku.edu/~jsv/Papers/Vit.IO_book.pdf）への参照数とキャッシュメモリ（https://en.wikipedia.org/wiki/Cache-oblivious_algorithm）の使用を考慮しています。計算が2つ以上のノード間で分割されている場合、それらのノード間の通信の複雑さは重要です（https://en.wikipedia.org/wiki/Communication_complexity）。ここにはいくつかの根本的な証明があります。

これらの対策間のリンクもあります。ほとんどの場合、ほぼすべてのリソースを使用すると時間がかかります。したがって、T単位を超えないものは、他のリソースのO（T）単位を超えないものがあります。 HartmanisとHopcroftによる "計算上の複雑さの理論の概要"という論文があります。これは、計算上の複雑さを堅固な数学的基礎に置きます。これは、計算複雑性尺度の非常に一般的な概念を定義しており、（定理4）は、「ある尺度で計算するのが容易な」関数が他の尺度で計算するのが容易であることを証明している。しかし、この結果（ほとんどの論文のように）は、現実の世界では必ずしも実用的な結果をもたらすとは限らない、数学的に抽象的な用語である。ここで使用されている2つの複雑さ間の接続は、ある測定値の多項式の複雑さが他の測定値の指数関数的な複雑さ（または悪化）である可能性があるほど十分に緩やかです。