프로그램의 길이와 양적 정보 측정을 위한 알고리즘 복잡성에 대한 통일된 추정

샤논 엔트로피와 콜모고로프 복잡성은 후자가 확률 분포를 기반으로 하는 반면, 전자는 프로그램 크기를 기반으로 하기 때문에 개념적으로 구별되는 두 가지 정보 메트릭입니다. 그러나 모든 재귀적 확률 분포는 결과적으로 상수에 따라 다르지만, 콜모고로프 복잡성 값은 그 샤논 엔트로피와 같습니다. 우리는 렌yi와 하브르다-차르바트 엔트로피의 순서 α 사이에 비슷한 상관관계가 존재하는지 조사하며, 이는 오직 렌yi와 하브르다-차르바트 순서 1의 엔트로피와만 일관되도록 합니다. 콜모고로프는 샤논 엔트로피와 알고리즘 복잡성의 특성이 비교 가능하다고 언급했습니다. 우리는 이러한 유사성의 한 측면을 조사합니다. 구체적으로, 샤논 엔트로피와 콜모고로프 복잡성에 대해 성립하는 선형 부등식입니다. 실제로 다음이 사실입니다: (1) 샤논 엔트로피에 대해 성립하는 모든 선형 부등식과 반대로 콜모고로프 복잡성에 대한 것; (2) 샤논 엔트로피에 대해 유한 부분집합의 선형 공간 랭크에 대해 성립하는 모든 선형 부등식; (3) 반대로는 사실이 아닙니다.