콜모고로프 복잡도

콜모고로프 복잡도(Kolmogorov complexity)는 문자열, 데이터 또는 다른 수학적 객체의 알고리즘적 정보량 또는 알고리즘적 무작위성을 측정하는 개념이다. 이는 러시아의 수학자 안드레이 콜모고로프(Andrey Kolmogorov)의 이름을 따서 명명되었지만, 이 개념은 레이 솔로모노프(Ray Solomonoff)와 마틴 초린(Martin Chaitin) 등에 의해서도 독립적으로 발표되었다. 따라서 알고리즘적 복잡도(Algorithmic complexity), 콜모고로프-초린 복잡도(Kolmogorov–Chaitin complexity), 알고리즘적 정보(Algorithmic information)라고도 불린다.

개념

콜모고로프 복잡도의 핵심 아이디어는 어떤 문자열을 생성하는 가장 짧은 컴퓨터 프로그램의 길이로 그 문자열의 정보량을 측정하자는 것이다. 만약 어떤 문자열이 짧은 프로그램으로 생성될 수 있다면, 그 문자열은 패턴이 있거나 규칙적이라고 할 수 있으며 복잡도가 낮다고 본다. 반대로, 문자열을 생성하는 가장 짧은 프로그램의 길이가 문자열 자체의 길이와 거의 같다면, 그 문자열은 압축하기 어렵고 무작위적이며 복잡도가 높다고 본다.

예를 들어, "0101010101010101"과 같이 01이 반복되는 긴 문자열은 "01을 8번 반복"과 같은 매우 짧은 프로그램으로 생성할 수 있다. 따라서 이 문자열의 콜모고로프 복잡도는 매우 낮다. 반면에, 무작위로 생성된 것처럼 보이는 매우 긴 문자열은 이를 설명하거나 생성하는 프로그램이 문자열 자체를 그대로 저장하고 출력하는 것 외에는 더 짧아지기 어려울 수 있다. 이런 문자열의 콜모고로프 복잡도는 높다.

정의

어떤 문자열 $s$의 콜모고로프 복잡도 $K(s)$는 미리 정해진 고정된 보편 튜링 기계 $U$를 사용하여 문자열 $s$를 출력하는 가장 짧은 프로그램 $p$의 길이 $|p|$로 정의된다. $$K(s)\; =\; \backslash min\; \{\; |p|\; \backslash colon\; U(p)\; =\; s\; \}$$ 여기서 $U(p)\; =\; s$는 보편 튜링 기계 $U$에 프로그램 $p$를 입력했을 때 출력으로 $s$를 얻는다는 의미이다.

불변성 정리

콜모고로프 복잡도의 정의는 사용하는 보편 튜링 기계 $U$에 의존하는 것처럼 보이지만, 중요한 '불변성 정리(Invariance theorem)'에 따르면 어떤 두 보편 튜링 기계 $U\_1$과 $U\_2$를 사용하더라도 임의의 문자열 $s$에 대해 $|K\_\{U\_1\}(s)\; -\; K\_\{U\_2\}(s)|\; \backslash le\; c$인 상수 $c$가 존재한다. 여기서 상수 $c$는 문자열 $s$와는 독립적이며, 사용된 두 보편 튜링 기계에만 의존한다. 즉, 기계 선택에 따른 복잡도의 차이는 문자열의 길이에 비해 무시할 수 있는 상수항에 불과하므로, 보편 기계를 고정하면 복잡도는 문자열의 본질적인 속성이 된다.

계산 불가능성

콜모고로프 복잡도는 모든 문자열에 대해 계산 가능한 함수가 아니다. 즉, 어떤 문자열의 정확한 콜모고로프 복잡도를 계산하는 일반적인 알고리즘은 존재하지 않는다. 이는 정지 문제(Halting Problem)의 비결정성과 관련이 있다. 특정 길이 $L$ 이하의 모든 프로그램을 실행해 보고 그중 $s$를 출력하는 가장 짧은 프로그램을 찾으려 해도, 일부 프로그램은 무한 루프에 빠져 끝나지 않을 수 있기 때문에 모든 경우를 유한 시간 안에 확인할 수 없다. 우리는 임의의 문자열에 대한 복잡도의 상한(예: 문자열을 그대로 출력하는 프로그램의 길이)은 알 수 있지만, 정확한 최솟값을 항상 구할 수는 없다.

알고리즘적 무작위성과의 관계

콜모고로프 복잡도는 '알고리즘적 무작위성(Algorithmic randomness)'을 수학적으로 엄밀하게 정의하는 데 사용된다. 문자열 $s$가 '알고리즘적으로 무작위'하다는 것은 그 콜모고로프 복잡도 $K(s)$가 문자열의 길이 $|s|$에 비례할 때(예: $K(s)\; \backslash ge\; |s|\; -\; c$인 상수 $c$가 존재할 때)를 의미한다. 즉, 알고리즘적으로 무작위인 문자열은 어떤 알고리즘으로도 그 길이보다 훨씬 짧게 압축하거나 효과적으로 예측할 수 없는 문자열이다. 이는 일반적인 통계적 무작위성 개념을 보완하는 더 깊은 수준의 무작위성을 나타낸다.

응용 및 중요성

• 정보 이론: 정보량의 근본적인 이론적 하한을 제공한다.
• 무작위성 정의: 알고리즘적 무작위성을 정의하고 연구하는 기초를 제공한다.
• 데이터 압축: 이론적으로 가능한 최적의 압축률의 한계를 보여준다.
• 추론 이론: 솔로모노프 유도(Solomonoff induction)와 같은 귀납적 추론 및 기계 학습 이론의 기반이 된다.
• 수학적 논리 및 재귀 이론: 수학적 객체의 복잡성 및 증명 가능성을 연구하는 데 사용된다.

콜모고로프 복잡도는 계산 불가능하다는 특성 때문에 실용적인 알고리즘 설계에 직접 적용하기는 어렵지만, 정보, 무작위성, 계산의 한계에 대한 깊은 이론적 통찰을 제공하는 중요한 개념이다.