本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #268
- 日期：2026-03-18
摘要
物件的有效複雜性的概念是其規律性的最小描述長度，這一概念是由蓋爾曼和勞埃德提出的。規律性透過係綜（即有限二進位串上的機率分佈）來建模。在我們先前的論文 [1] 中，我們用演算法資訊理論的精確術語提出了有效複雜性的定義。在這裡，我們研究由固定的、通常不可計算的過程產生的二進位字串的有效複雜性。我們表明，在不太強烈的條件下，長的典型過程實作實際上是簡單的。我們的結果在粗略有效複雜性的背景下變得最透明，這是對有效複雜性原始概念的修改，在定義中使用了更少的參數。 Antunes 和 Fortnow 提出了複雜性相關概念的類似修改。