為什麼記憶硬函式依賴於時空權衡？
我最近在閱讀有關記憶困難的功能。在我閱讀的那些論文中，他們幾乎總是引入這樣的時空權衡：
$$ S(n) \times T(n) \in \Omega(\mathrm{Poly}(n)) $$ 我了解記憶體硬函式正在嘗試使用大量記憶體來應對 ASIC 攻擊。但我不明白為什麼必須通過時空權衡來衡量大量記憶體使用。
有一些問題被證明是記憶體密集型的（至少是同類中最密集的記憶體）。搜尋PSPACE和EXPSPACE將返回結果列表。
計算複雜性告訴我們，如果一個問題需要大量記憶體來執行，那麼它也需要大量時間來執行。難道這些問題不會比那些有時間-空間權衡的問題更好地用作記憶硬函式嗎？
為了創建這樣一個函式，你需要用一些計算的結果來填充記憶體；然後，memory-hard 函式讀取這些值以在以後進一步計算。
理論上可以在需要時重新計算它們，而不是保存這些值。所以記憶體並不是一個硬性要求。然而，記憶硬函式是以這樣一種方式建構的，即它們需要更多的計算而不需要記住中間值。這是時間/記憶體的權衡。
確實，許多記憶體硬函式 (MHF) 只提供了時空折衷。以 為例
scrypt，它被證明具有最佳的累積記憶體複雜度 $ \Omega(n^2) $ 在：Joël Alwen 和 Binyi Chen 和 Krzysztof Pietrzak 和 Leonid Reyzin 和 Stefano Tessaro：Scrypt 是最難記憶的。歐洲加密貨幣 2017
累積記憶體複雜度僅計算算法長度內的記憶體使用總和。它不排除算法採用 $ O(n^2) $ 時間，但只有 $ O(1) $ 空間，確實不難看出
scrypt確實有這樣的算法。據我了解，這就是大多數 ASIC 的實現方式，因此“最佳記憶體硬度”（自相矛盾）並不能阻止人們使用基本上不使用記憶體的方式對其進行評估。這種奇怪的情況激發了對記憶體硬度的更細粒度的定義，例如持續的記憶體複雜性：
Joel Alwen 和 Jeremiah Blocki 以及 Krzysztof Pietrzak：持續的空間複雜性。歐洲加密貨幣 2018。
持續的複雜性允許你說“評估這個你必須使用的函式” $ \Omega(n/\log n) $ 記憶體量 $ \Omega(n) $ 步驟。”所以這是朝著你建議的方向邁出的一步。
要回答您的具體問題：
計算複雜性告訴我們，如果一個問題需要大量記憶體來執行，那麼它也需要大量時間來執行。難道這些問題不會比那些有時間-空間權衡的問題更好地用作記憶硬函式嗎？
這比看起來更重要。MHF 的要求存在困難的不對稱性：
- 誠實算法是一種順序算法，它使用 $ n $ 時間和 $ n $ 記憶
- 沒有並行算法使用顯著少於 $ n $ 時間， $ n $ 空間（理想情況下同時需要兩者）
因此，您必須找到一種方法來排除並行化帶來的加速。實際上比這更糟糕，因為您還想排除攤銷的加速（解決 $ k $ 實例較少 $ \alpha n $ 時間和 $ \beta n $ 記憶為 $ \alpha \beta < k $ ).