---
id: wiki-2026-0508-kolmogorov-complexity
title: Kolmogorov Complexity
category: 10_Wiki/Topics
status: verified
canonical_id: self
aliases: [Algorithmic Complexity, Descriptive Complexity, K-complexity]
duplicate_of: none
source_trust_level: A
confidence_score: 0.95
verification_status: applied
tags: [complexity, information-theory, computability, algorithmic-information]
raw_sources: []
last_reinforced: 2026-05-10
github_commit: pending
tech_stack:
  language: python
  framework: zlib, lzma
---

# Kolmogorov Complexity

## 매 한 줄
> **"매 string 의 shortest description length"**. Kolmogorov Complexity $K(x)$ 는 universal Turing machine 위에서 string $x$ 를 출력하는 shortest program 의 length. Solomonoff (1960), Kolmogorov (1965), Chaitin (1969) 이 독립적으로 정의했고, 2026 ML 에서는 generalization bounds, MDL, AIXI agents 의 theoretical foundation.

## 매 핵심

### 매 Definition
- $K_U(x) = \min \{ |p| : U(p) = x \}$
- $U$ = universal Turing machine
- invariance theorem: $|K_U(x) - K_{U'}(x)| \le c$ — choice 무관 up to constant
- **uncomputable** — no algorithm computes $K(x)$ for arbitrary $x$

### 매 Variants
- **Plain $C(x)$**: any halting program
- **Prefix $K(x)$**: prefix-free programs (Levin)
- **Conditional $K(x|y)$**: given $y$ as input
- **Time-bounded $K^t(x)$**: program runs in ≤ $t$ steps

### 매 응용
1. **MDL principle**: model selection — pick shortest description.
2. **Solomonoff prior**: $P(x) \propto 2^{-K(x)}$.
3. **Lossless compression**: practical lower bound.
4. **Randomness test**: $K(x) \approx |x|$ ⟺ random.
5. **AIXI**: optimal universal agent.

### 매 Properties
- $K(x) \le |x| + O(1)$ — copy verbatim
- $K(xy) \le K(x) + K(y) + O(\log)$
- most strings are incompressible (Counting argument)
- Chaitin's $\Omega$ — halting probability, encodes K

## 💻 패턴

### Compression-based estimate
```python
import zlib, lzma

def K_approx(x: bytes, codec="lzma") -> int:
    if codec == "zlib":
        return len(zlib.compress(x, 9))
    return len(lzma.compress(x, preset=9 | lzma.PRESET_EXTREME))

# normalized
def NCD(x: bytes, y: bytes) -> float:
    """Normalized Compression Distance — Cilibrasi & Vitanyi 2005"""
    Kx, Ky = K_approx(x), K_approx(y)
    Kxy = K_approx(x + y)
    return (Kxy - min(Kx, Ky)) / max(Kx, Ky)
```

### MDL model selection
```python
def mdl_score(model, data):
    # L(model) = bits to describe model
    # L(data|model) = bits to encode data given model
    return code_length(model) + code_length(data, given=model)

best = min(candidates, key=lambda m: mdl_score(m, data))
```

### Solomonoff prior approximation (Levin search)
```python
def levin_search(input, target, max_t):
    """enumerate programs by 2^|p| * t — Levin's universal search"""
    for budget in range(1, max_t):
        for p in enumerate_programs(max_len=int(np.log2(budget))):
            if simulate(p, input, steps=budget // (2**len(p))) == target:
                return p
```

### Compression-based clustering
```python
from sklearn.cluster import AgglomerativeClustering
import numpy as np

dist = np.array([[NCD(xi, xj) for xj in docs] for xi in docs])
labels = AgglomerativeClustering(
    metric="precomputed", linkage="average", n_clusters=k
).fit_predict(dist)
```

### Random string detector
```python
def is_likely_random(x: bytes, threshold=0.95) -> bool:
    return K_approx(x) / len(x) > threshold  # near-incompressible
```

## 매 결정 기준
| Need | Tool |
|---|---|
| theoretical proof | $K$ definition |
| practical estimate | LZMA / zstd compress length |
| similarity | NCD |
| model selection | MDL / BIC |
| online learning | Solomonoff (intractable, approximate) |

**기본값**: LZMA approximation for compute, MDL for principled selection.

## 🔗 Graph
- 부모: [[Information_Theory|Information-Theory]]
- 변형: [[MDL]]
- 응용: [[Compression]]
- Adjacent: [[Shannon-Entropy]]

## 🤖 LLM 활용
**언제**: model complexity reasoning, compression-as-intelligence arguments, generalization theory.
**언제 X**: 매 production code path — uncomputable, only bounds.

## ❌ 안티패턴
- **Treating K as computable**: 매 K(x) 의 exact value 사용 시도.
- **Compressor-specific bound 절대화**: gzip approximation 은 매 noisy upper bound.
- **NCD 의 metric assumption**: NCD 는 매 quasi-metric — triangle inequality 약하게 only.
- **Confusing K with Shannon H**: K is per-string, H is distributional.

## 🧪 검증 / 중복
- Verified (Li & Vitanyi 2019 4th ed textbook, Hutter 2005 AIXI book, Chaitin 1987 algorithmic info theory).
- 신뢰도 A.

## 🕓 Changelog
| 날짜 | 변경 |
|---|---|
| 2026-05-08 | Phase 1 |
| 2026-05-10 | Manual cleanup — K definition, MDL, NCD, Solomonoff, AIXI |
