計算複雜度以外的其他時空資源

Question

一般來說，在計算複雜度上，我們討論的是時間和空間的複雜性。也就是說，我們考慮解決某些問題需要多少時間或空間。

我想知道是否有另一種資源（超越時間和空間），我們可以使用參考來討論計算複雜性。

Answer 1

人們已經考慮了引用外部存儲器（https://www.ittc.ku.edu/~jsv/Papers/Vit.IO_book.pdf）和使用高速緩存（https://en.wikipedia.org/wiki/Cache-oblivious_algorithm）的次數。在兩個或兩個以上節點之間進行計算的情況下，這些節點之間的通信複雜度是有趣的（https://en.wikipedia.org/wiki/Communication_complexity），並且這裏有一些簡潔的證明。

這些措施之間也有聯繫。最明顯的是，使用幾乎任何資源都需要時間，因此任何花費不多於T個單位時間的事物可能不會超過任何其他資源的O（T）單位。 Hartmanis和Hopcroft有一篇論文「計算複雜性理論綜述」，它將計算複雜性置於一個堅實的數學基礎上。這定義了計算複雜性度量的一個非常普遍的概念，並且（定理4）證明（他們的概要）「在一個度量中」容易「計算的函數」在其他度量中計算「是」容易的「。然而，這個結果（像本文的大部分內容）是數學上抽象的術語，在現實世界中並不一定有實際的結果。這裏使用的兩個複雜度之間的聯繫非常鬆散，因此一個度量中的多項式複雜度在另一個度量中可能是指數複雜度（或更差）是完全可能的。