# 콜모고로프-차이틴 복잡도 (Kolmogorov-Chaitin Complexity)

콜모고로프-차이틴 복잡도(Kolmogorov–Chaitin complexity, 줄여서 콜모고로프 복잡도 K(x))는 고정된 범용 컴퓨터(범용 튜링 기계)에서 문자열 x를 출력하고 멈추는 가장 짧은 프로그램의 길이입니다. 1960년대에 솔로모노프, 콜모고로프, 차이틴이 각각 독립적으로 발전시킨 개념으로, '데이터를 설명하는 데 필요한 최소 정보량'을 개별 문자열 단위로 정의합니다.

## 자세히 알아보기

'01'을 50만 번 반복한 100만 비트 문자열은 "01을 50만 번 출력하라"는 짧은 프로그램으로 만들 수 있어 복잡도가 낮습니다. 반면 동전을 100만 번 던진 결과는 대개 그 비트들을 그대로 적는 것보다 짧게 설명할 방법이 없어, 복잡도가 길이와 비슷합니다. 이렇게 자기 길이보다 짧게 압축할 수 없는 문자열을 '알고리즘적으로 무작위'라고 합니다. 세는 논증으로 보면 길이 n인 문자열 대부분은 거의 압축되지 않습니다.

어떤 범용 컴퓨터(프로그래밍 언어)를 쓰느냐에 따라 값이 상수만큼만 달라진다는 불변성 정리가 이 개념을 의미 있게 만듭니다. 그러나 K(x)는 계산 불가능합니다. 정지 문제와 같은 이유로, 임의의 문자열에 대해 정확한 값을 구하는 알고리즘은 존재하지 않습니다. 실무에서는 압축 프로그램의 출력 길이를 상한 추정치로 씁니다.

섀넌 엔트로피가 '확률 분포'의 평균 정보량이라면, 콜모고로프 복잡도는 '개별 문자열'의 정보량입니다. 두 개념은 평균적으로 서로 가까워집니다.

## 블록체인·암호화폐에서는

- 의사난수의 역설: 암호학적 의사난수 생성기가 만든 1GB의 출력은 '생성기 코드 + 256비트 시드'라는 짧은 프로그램으로 만들 수 있으므로 콜모고로프 복잡도가 매우 낮습니다. 그런데도 시드를 모르는 사람에게는 진짜 난수와 구별되지 않습니다. 그래서 현대 암호학은 콜모고로프 복잡도가 아니라 '효율적인 공격자가 구별할 수 있는가'라는 계산적 정의를 씁니다.
- HD 지갑: BIP-32 HD 지갑은 니모닉 시드 하나에서 거의 무한한 수의 키를 결정론적으로 만들어 냅니다. 수많은 키 전체의 정보량이 결국 시드 하나(128~256비트)에 담겨 있다는 뜻이며, 시드만 지키면 되지만 시드가 유출되면 모든 키가 노출되는 이유이기도 합니다.
- 통계 검정의 한계: NIST SP 800-22에도 압축 가능성과 관련된 마우러의 범용 통계 검정이 들어 있지만, 통과했다고 '무작위'가 증명되는 것은 아닙니다.

## 쉽게 말하면

콜모고로프 복잡도는 '이 데이터를 전화로 불러 주려면 최소한 몇 마디가 필요한가'입니다. 규칙이 있으면 짧게, 없으면 통째로 불러야 합니다.

## 예시

'aaaa…a'(100만 개)는 "a를 100만 번"으로 수십 바이트면 충분하지만, 무작위 100만 글자는 거의 100만 글자가 다 필요합니다.

---
출처: https://achivx.kr/glossary/kolmogorov-chaitin-complexity-%EC%BD%9C%EB%AA%A8%EA%B3%A0%EB%A1%9C%ED%94%84-%EC%B0%A8%EC%9D%B4%ED%8B%B4-%EB%B3%B5%EC%9E%A1%EB%8F%84/ · ACHIVX 용어 사전 · 수정일 2026-10-20