콜모고로프 복잡도

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

알고리즘 정보이론에서 콜모고로프 복잡도는 유한한 길이를 가진 데이터 열의 복잡성을 나타내는 지표 중 하나로서, 출력결과가 그 데이터에 일치하는 프로그램의 길이의 최솟값을 정의한다. 1963년 이것을 주제로 하여 발표한 안드레이 콜모고로프의 이름을 따서 지었으나 이보다 먼저 레이 솔로모노프(Ray Solomonoff)에 의해 제시된 바 있다.[1][2]

이 그림은 망델브로 집합 프랙털의 일부를 나타낸다. 이 그림의 각각의 픽셀의 24비트 색상을 저장하는 것만 해도 백62만 비트가 필요하다. 하지만 작은 컴퓨터 프로그램이 망델브로 집합의 정의를 사용하여 표현할 수 있으며 이미지의 코너를 조정할 수 있다. 그러므로 이 그림을 인코딩한 비압축 파일의 코모고르프 복잡성은 162만 보다 작다.

정의[편집]

예컨대 32개의 문자로 이루어진

abababababababababababababababab,
4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

라는 두 문자열을 생각해보자.

1번째 문자열은 영어에서 "write ab 16 times"라는 17자의 짧은 표현으로 나타내어질 수 있는데 반해 2번째 문자열은 "write 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"라고 전부를 그대로 쓰는 것보다 더 간단한 표현을 찾기 힘들다. 따라서 첫번째 문자열이 두번째 것보다 더 '복잡도가 낮다'고 생각할 수 있다.

형식적으로 말해서 어떤 튜링 완전한 정의언어가 있을 때 어떠한 문자열의 콜모고로프 복잡도는 그 언어에서 그 문자열을 정의하는 표현 중 가장 짧은 것의 길이이다. (이때 정의 언어가 무엇인지는 크게 중요하지 않은데 그 이유는 불변성 정리에 의해 주어진다.)

여기서 문자열의 '정의'(description)이라고 함은 예를 들어 프로그래밍 언어에서 그 문자열을 output으로 내어놓는 프로그램을 이야기한다고 정의될 수도 있고, 이러한 정의는 더욱 일반화될 수 있다. 그러므로 어떤 문자열 s가 있을때, 어떤 언어에서 그 문자열을 정의하는 가장 짧은 프로그램(글)을 최단 정의 d(s), 그 길이를 K(s) 곧 콜모고로프 복잡도(Kolmogorov complexity)로 정의한다.

불변성 정리[편집]

서로 다른 정의언어 L1, L2 를 생각하자. 이때 L1과 L2 각각에 대한 문자열 x의 콜모고로프 복잡도의 차이는 문자열 x와 무관하게 정의언어의 종류에 의해서만 결정되는 특정한 상수보다 항상 작다. 비형식적으로 말해서, 문자열 x를 출력하는 서로 다른 언어로 쓰여진 프로그램의 길이 차에는 x의 길이와 무관하게 상한이 존재한다는 것이다. 이를 불변성 정리(invariance theorem) 라고 한다. 따라서 콜모고로프 복잡도를 다룰 때 일반적으로 정의언어를 따로 고려하지 않아도 무방하다.

증명은 다음과 같다. L2에서 최단 표현을 d2라 할때 d1은 적어도 d2에 L2에서 L1로의 번역을 제시하는 해석(인터프리터)을 더한 것의 길이보다 같거나 작으므로 그러한 해석의 길이를 c라 하면 K1 ≤ K2 + c 가 증명된다.

계산불가능성[편집]

콜모고로프 복잡도는 계산불가능한 함수이다. 흔히 문자열 s에 대한 콜모고로프 복잡도 K(s)를 다음과 같이 구성해보려 시도해볼 수 있다.

function KolmogorovComplexity(string s)
    for i = 1 to infinity:
        for each string p of length exactly i
            if isValidProgram(p) and evaluate(p) == s
                return i

즉, 각 유한한 길이에 대해 무작위로 프로그램을 생성하여 그 프로그램이 s를 내어놓으면 정지하여 그 길이를 내어놓는 함수를 생각한다고 하자. 문제는 이 함수가 무작위로 프로그램을 구성하는 도중 영원히 정지하지 않는 프로그램을 구성하여 나아가지 못하고 무한히 머무르게 되리라는 점에 있다. 또한 정지 문제에 관해 알려진 바 프로그램을 실행하기 전에 그 프로그램의 정지 여부를 판정하는 일률적인 방법은 없다.

정확한 증명은 다음과 같이 행해질 수 있다. 어떠한 언어와 그 인터프리터를 가정하고 인터프리터의 길이를 예컨대 1,400,000 이라 하자. 귀류법을 위해 문자열 s를 받아 그 복잡도를 내어놓는 KolmogorovComplexity(s)라는 함수의 존재를 가정한다. 모든 프로그램은 길이가 유한하므로 이 함수의 길이 7,000,000,000 를 가정한다. 그렇다면 다음과 같이 점점 긴 문자열을 KolmogorovComplexity에 대입한 결과를 보고 그것이 처음으로 (복잡도 함수의 길이보다 긴) 8,000,000,000 을 넘을때 정지하고 s를 내어놓는 함수를 구성할 수 있다.

function GenerateComplexString()
    for i = 1 to infinity:
        for each string s of length exactly i
            if KolmogorovComplexity(s) ≥ 8000000000
                return s

이는 8,000,000,000 보다 짧은 길이의 프로그램으로는 정의될 수 없는 문자열 중 가장 짧은 문자열 s를 내어놓는 함수가 된다. 그런데 이 프로그램의 길이는 KolmogorovComplexity(s)의 길이 + 함수 기타 부분의 길이 + 인터프리터의 길이 = 7,001,401,288 가 나오며, 길이가 8,000,000,000 보다 짧은 이 프로그램이 s를 내어놓는다는 것은 모순이다.

이러한 증명은 "한글 60자 내로 정의되지 않는 가장 짧은 수"를 정의할때 모순이 나온다는 베리의 역설과 비슷한 방식이다.

차이틴의 불완전성 정리[편집]

K(s)의 상한은 임의의 문자열 s를 write "s"로 정의할 수 있으므로 언어에 따라 자연스럽게 |s| + c(일반적으로 크지 않은 상수)로 정해진다. 한편 s가 압축가능(compressible)하다 함은 K(s)가 |s| + c보다 작아진다는 것으로 정의할 수 있다.

차이틴의 불완전성 원리(Chaitin's incompleteness theorem)에 의하면, 문자열이 압축가능한지의 여부는 문자열의 복잡도가 일정치를 넘으면 형식적으로 증명불가능하다.

각주[편집]

  1. Kolmogorov, Andrey (1963). “On Tables of Random Numbers”. 《Sankhyā Ser. A.》 25: 369–375. MR 178484. 
  2. Kolmogorov, Andrey (1998). “On Tables of Random Numbers”. 《Theoretical Computer Science》 207 (2): 387–395. doi:10.1016/S0304-3975(98)00075-9. MR 1643414. 

외부 링크[편집]