콜모고로프 복잡도

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

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

정의[편집]

어떤 범용 정의언어에 대해서 문자열의 콜모고로프 복잡도는 그 문자열의 가능한 표현중 가장 짧은 표현이다.(정의 언어의 선택과는 큰 연관성이 없다.) 그렇기 때문에 문자열의 콜모고로프 복잡도는 그 문자열의 길이보다 작아질 수 없다.

불변성 정리[편집]

서로 다른 정의언어 f,g 를 생각하자. 이때 f 와 g 각각에 대한 문자열 x의 콜모고로프 복잡도의 차이는 문자열 x와 관계없는 상수보다 항상 작다. 비형식적으로, 문자열 x를 출력하는 서로다른 언어로 쓰여진 프로그램의 길이는 x의 길이와 무관한 상한이 존재한다는 것이다. 이를 불변성 정리(The Invariance 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. MR 1643414. doi:10.1016/S0304-3975(98)00075-9. 

외부 링크[편집]