本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #369
- 日期：2026-03-18
摘要
有效複雜度衡量物件規律性的資訊內容。它由 M. Gell-Mann 和 S. Lloyd 引入，以避免 Kolmogorov 複雜性（也稱為演算法資訊內容）的一些缺點。在本文中，我們給出了有效複雜性的精確形式定義，並對其基本屬性進行了嚴格的證明。特別是，我們證明了不可壓縮的二進位字串實際上是簡單的，並且我們證明了具有與其長度接近的有效複雜性的字串的存在。此外，我們表明有效複雜性與 Bennett 的邏輯深度相關：如果字串的有效複雜性超過某個明確的閾值，那麼該字串必須具有天文數字般的深度；否則，深度可以任意小。