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