Kolmogorov의 복잡도에 대한 최적의 알려진 상한선은 무엇입니까?

Question

infinite time이 주어지면 문자열의 정확한 Kolmogorov complexity에 접근 할 수 있습니다. 우리는 무한한 시간이 없다면, 우리는 여전히 문자열의 콜 모고 로프의 복잡성에 상한을 계산할 수 있습니다

... 단순히 문자열 s를 선택한 언어에 대응하는 압축 해제를 구현하고, 어떤 방법으로 압축 바인딩 엄격한 상부 제공 - 일정한 시간 내에 종료하도록 보장 -

(Wikipedia)를 알고리즘 있는가 ... 압축 문자열을 압축 해제를 연결하여, 생성 된 문자열의 길이를 측정 Kolmogorov 복잡도보다 len(compressed string) + len(decompressor)?

Answer 1

불행히도 K (x)는 근사치가 아닙니다. 상한은 없습니다. 파이 압축하는 것을 고려하십시오. pi를 생성하는 작은 프로그램이 있으므로 K (pi)는 매우 작습니다. 그러나 "표준"압축 프로그램 (zip, etc ...)은 pi를 많이 압축 할 수 없습니다. 따라서 compress (pi)는 크다. 임의로 커진다. 그러므로 compress (pi) - K (pi)는 제한이 없다.

다른 말로하면, 작은 K (x)가 얼마나 될 수 있는지 알 수 없으므로 근사치에 상한을 둘 수는 없습니다.