本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
非平衡統計力學的最新進展使人們對計算的熱力學成本有了比蘭道爾提出的更深入的理解，然後在計算複雜性社區中進行了廣泛的研究。特別是，蘭道爾的工作引起了對計算中位數擦除數量的關注，因為它與輸入和輸出之間的熵變化有關。然而，物理學的新進展|已被實驗證實|意味著我們現在可以計算額外的熱力學成本，而不僅僅是輸入和輸出之間熵的變化。因此，我們現在了解到，雖然邏輯可逆計算可以帶來一些熱力學優勢，但這還遠遠沒有結束。本文的目的是強調由於考慮這些新的熱力學成本而提出的計算複雜性方面的新的開放性問題。除了導致對邏輯可逆性優點的修正觀點之外，這些問題還涉及隨機演算法、平均情況複雜性、糾錯碼的熱力學成本以及雜訊/不精確/近似計算。