Kolmogorov 복잡성에 대한 체인 규칙

이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오.(2014년 7월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

Kolmogorov 복잡성에 대한 체인 규칙은^{[citation needed]} 정보 엔트로피에 대한 체인 규칙의 아날로그로, 다음과 같이 명시한다.

${\displaystyle H(X,Y)=H(X)+H(Y X)}$

즉, 두 시퀀스 X와 Y의 조합된 랜덤성은 X의 랜덤성과 X를 알고 나면 Y에 남겨지는 임의의 랜덤성의 합이다.이는 조건부 엔트로피와 관절 엔트로피의 정의에서 바로 따르며, 결합 확률은 한계 확률과 조건부 확률의 산물이라는 확률론에서 나온 사실에 따른 것이다.

${\displaystyle P(X,Y)=P(X)P(Y X)}$

${\displaystyle \Rightarrow \log P(X,Y)=\log P(X)+\log P(Y X)}$

Kolmogorov 복잡성에 대한 등가 문장은 정확하게 유지되지 않는다. 이는 로그 용어까지만 해당된다.

${\displaystyle K(x,y)=K(x)+K(y x)+O(\log(x,y))}$

(정확한 버전인 KP(x, y) = KP(x) + KP(y x*) + O(1)는 접두사 복잡성 KP를 유지하며, 여기서 x*는 x를 위한 최단 프로그램이다.)

그것은 X와 Y를 인쇄하는 가장 짧은 프로그램을 X가 주어진 프로그램인쇄 Y와 결합하여 얻을 수 있으며, 게다가 최대 로가리듬 인자를 더하여 얻을 수 있다고 기술하고 있다.결과는 Kolmogorov 복잡성에 대한 상호 정보의 아날로그인 알고리즘 상호 정보가 대칭적이라는 것을 암시한다: I(x:y) = I(y:x) + O(log K(x,y) 모든 x,y.

증명

≤ 방향은 명확하다: x를 제작하기 위한 프로그램을 연계하여 x와 y를 제작할 수 있는 프로그램, x에 대한 접근 권한을 부여하는 y를 제작할 수 있는 프로그램, 그리고 (로그 용어) x와 y(log(k(x, y) 이 길이)에 대한 두 프로그램을 어디에 분리해야 하는지 알 수 있도록 프로그램 중 하나의 길이를 제작할 수 있다.

≥ 방향의 경우, k+l = K(x,y)와 같이 모든 k,l에 대해 다음 중 하나를 가지는 것으로 충분하다.

K(x k,l) ≤ k + O(1)

또는

K(y x,k,l) ≤ l + O(1)

길이가 정확히 K(x,y)인 프로그램에 의해 생산된 모든 쌍(a₁,b₁), (a₂,b₂), ..., (a_e,b_e)의 목록을 고려한다 [hence K(a,b) ≤ K(x,y)].이 목록은

• 쌍(x,y) 포함
• k와 l(길이 K(x,y)의 모든 프로그램을 병렬로 실행하여)를 열거할 수 있다.
• 최대 2개의^K(x,y) 요소가 있다(길이 n의 프로그램이 최대 2개ⁿ 있기 때문이다).

첫째, x가 첫 번째 요소로 2회^l 미만 나타난다고 가정한다.우리는 (a₁,b₁), (a₂,b₂), ...를 열거한 다음 (x,b)의 하위 목록에서 (x,y)를 선택하여 y 주어진 x,k,l을 지정할 수 있다.가정으로, 이 하위 목록에서 (x,y)의 지수는 2 미만이며^l, 따라서 y에 주어진 길이 l + O(1) x,k,l의 프로그램이 있다.자, x가 첫 번째 요소로 적어도 두^l 번 나타난다고 가정합시다.이것은 최대 2^K(x,y)-l = 2개의^k 다른 문자열에서 발생할 수 있다.이러한 문자열은 k,l로 열거할 수 있으며 따라서 x는 이 열거에서 그것의 색인으로 지정될 수 있다.x에 해당하는 프로그램의 크기는 k + O(1)이다.정리가 증명했다.

참조

• Li, Ming; Vitányi, Paul (February 1997). An introduction to Kolmogorov complexity and its applications. New York: Springer-Verlag. ISBN 0-387-94868-6.

• Kolmogorov, A. (1968). "Logical basis for information theory and probability theory". IEEE Transactions on Information Theory. Institute of Electrical and Electronics Engineers (IEEE). 14 (5): 662–664. doi:10.1109/tit.1968.1054210. ISSN 0018-9448.

• Zvonkin, A K; Levin, L A (1970-12-31). "The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms". Russian Mathematical Surveys. IOP Publishing. 25 (6): 83–124. doi:10.1070/rm1970v025n06abeh001269. ISSN 0036-0279.