엔트로피 압축

Entropy compression

수학과 이론 컴퓨터 과학에서 엔트로피 압축은 로빈 모서가 원래 로바스 지방 보조마사의 알고리즘 버전을 증명하기 위해 사용한 무작위 과정이 종료된다는 것을 증명하기 위한 정보 이론적 방법이다.[1][2]

설명

이 방법을 이용하기 위해서는 주어진 프로세스의 이력을 효율적으로 기록할 수 있다는 것을 증명한다. 즉, 어떤 과거의 공정 상태를 현재의 상태와 이 기록에서 회복할 수 있고, 프로세스의 각 단계에서 기록되는 추가 정보의 양이 (평균적으로) 의 양보다 적다는 것이다.각 단계에서 무작위로 생성되는 새로운 정보결과적으로 증가하는 총 정보 콘텐츠의 불일치는 결코 현 상태의 고정된 정보의 양을 초과할 수 없으며, 이 정보로부터 프로세스가 결국 종료되어야 한다.이 원리는 Kolmogorov 복잡성을 이용하여 공식화하고 엄격하게 만들 수 있다.[3]

예

Fortnow와[3] Tao에[4] 의해 제시된 예는 균일한 절 크기를 가진 결합 정상 형태의 Boolean 공식에 대한 Boolean 만족도 문제에 관한 것이다.이러한 문제들은 두 개의 숫자(k,t)로 매개변수가 될 수 있다. 여기서 k는 조항당 변수 수이고 t는 어떤 변수가 나타날 수 있는 다른 조항들의 최대 수입니다.변수가 임의로 참 또는 거짓으로 지정되면, 절이 만족되지 않는 사건은 확률 2로−k 발생하며, 각 사건은 r = k(t - 1) 이외의 모든 사건과 독립적이다.R < 2/ek(여기서 e는 자연 로그의 기초)를 만들 정도로 t가 작을 경우 해결책이 항상 존재한다는 것을 Lovassz 로컬 보조정리기로부터 따른다.r이 이 경계보다 상수 인자에 의해 작을 때 그러한 해결책을 찾기 위해 엔트로피 압축을 사용하여 다음과 같은 알고리즘을 나타낼 수 있다.

  • 임의의 진실 할당 선택
  • 불만족스러운 조항 C가 존재하지만, C를 인수로 하여 재귀적 서브루틴 수정안을 호출한다.이 서브루틴은 C의 변수에 대해 새로운 무작위 진실 할당을 선택한 다음, C와 변수를 공유하는 모든 불만족 조항(C 자체를 포함)에 대해 동일한 서브루틴을 반복적으로 호출한다.

이 알고리즘은 입력 공식이 만족스럽지 않으면 종료될 수 없으므로, 입력 공식이 종료된다는 증거도 솔루션이 존재한다는 증거다.외부 루프의 각 반복은 불만족 절의 수를 감소시키므로(다른 어떤 조항도 불만족하게 하지 않고 C가 만족하게 되는 원인이 된다) 핵심 문제는 수정 서브루틴이 종료되는지 또는 무한 재귀에 들어갈 수 있는지가 된다.[3]

이 질문에 답하려면 한편으로는 수정 서브루틴의 각 반복에서 생성된 무작위 비트 수(절당 k비트)와 다른 한편으로는 과거 상태가 생성될 수 있는 방식으로 이 알고리즘의 기록을 기록하는 데 필요한 비트 수를 고려하십시오.이 이력을 기록하기 위해 우리는 현재의 진실 할당(n 비트), 수정 서브루틴에 대한 초기 인수의 순서(m log m 비트, 여기서 m은 입력에 포함된 절의 수)를 저장한 다음, 수정하기 위한 재귀적 호출을 반환하였거나 또는 수정하기 위한 재귀적 호출을 r + 1 조항 중 하나에 차례로 호출하였음을 나타내는 일련의 기록을 저장할 수 있다.변수를 C와 공유하는 (C 자체 포함)레코드당 r + 2개의 가능한 결과가 있으므로 레코드를 저장하는 데 필요한 비트 수는 로그 r + O(1)이다.[3]

이 정보는 고쳐야 할 재귀적 주장으로 주어진 절의 순서를 회복하는 데 사용될 수 있다.이 과정의 각 단계의 진실 배정은 각 조항이 각 수정 통화 이전에 모든 변수의 값을 추론하기 위해 이전에 불만족스러웠다는 사실을 이용하여 이 일련의 조항들을 통해 거꾸로 진행함으로써 (추가 정보를 기록할 필요 없이) 회복될 수 있다.따라서 f 호출 후 수정하기 위해 알고리즘은 fk 랜덤 비트를 생성하지만 m log m + n + f log r + O(f) 비트만 사용하는 기록에서 전체 이력(생성된 비트 포함)을 복구할 수 있다.따라서, r이 로그 r + O(1) < k를 만들 정도로 충분히 작을 때, 수정 서브루틴은 전체 알고리즘의 과정에 걸쳐 O(m log m + n) 재귀 호출만 수행할 수 있다.[3]

역사

"엔트로피 압축"이라는 이름은 테렌스 타오가[4] 블로그에 올린 글에서 이 방법에 붙여졌고, 이후 다른 연구자들에 의해 이 방법에 사용되어 왔다.[5][6][7]

모서의 알고리즘 로바스 지방 보조정리 원본은 이 방법을 사용하여 원래 로바스 지방 보조정리보다 약한 한계를 달성했는데, 원래 로바스 지방 보조정리법은 그것이 존재를 증명하는 대상을 찾는 건설적인 방법 없이 존재 정리로서 공식화되었다.이후 모저와 가보르 타도스는 같은 방법을 사용해 원래의 보조정리범위에 맞는 알고리즘 로바스즈 로컬 보조정리 버전을 입증했다.[8]

엔트로피 압축법의 발견 이후, 그것은 또한 로바스 지방 보조정리법에 의해 주어질 수 있는 것보다 더 강한 어떤 문제들에 대한 경계를 달성하기 위해 사용되었다.예를 들어, 최대 Δ가 있는 그래프의 반복 엣지 컬러링 문제에 대해서는, 64 Δ의 색상이 항상 존재하는 것이 국부 보조마사를 사용하여 처음 나타났고, 후에 국부 보조마사의 보다 강력한 버전을 사용하여 9.62 Δ로 개선되었다.그러나 엔트로피 압축을 사용한 보다 직접적인 인수는 4 Δ - 1) 색상만 사용하는 색상이 존재한다는 것을 보여주며, 더욱이 이 색상은 무작위화된 다항식 시간에서 찾을 수 있다.[6]

참조

  1. ^ Moser, Robin A. (2009), "A constructive proof of the Lovász local lemma", STOC'09—Proceedings of the 2009 ACM International Symposium on Theory of Computing, New York: ACM, pp. 343–350, arXiv:0810.4812, doi:10.1145/1536414.1536462, MR 2780080.
  2. ^ Lipton, R. J. (June 2, 2009), "Moser's Method of Bounding a Program Loop", Gödel's Lost Letter and P=NP.
  3. ^ a b c d e Fortnow, Lance (June 2, 2009), "A Kolmogorov Complexity Proof of the Lovász Local Lemma", Computational Complexity.
  4. ^ a b Tao, Terence (August 5, 2009), "Moser's entropy compression argument", What's New.
  5. ^ Dujmović, Vida; Joret, Gwenaël; Kozik, Jakub; Wood, David R. (2011), Nonrepetitive Colouring via Entropy Compression, arXiv:1112.5524, Bibcode:2011arXiv1112.5524D.
  6. ^ a b Esperet, Louis; Parreau, Aline (2013), "Acyclic edge-coloring using entropy compression", European Journal of Combinatorics, 34 (6): 1019–1027, arXiv:1206.1535, doi:10.1016/j.ejc.2013.02.007, MR 3037985.
  7. ^ Ochem, Pascal; Pinlou, Alexandre (2014), "Application of entropy compression in pattern avoidance", Electronic Journal of Combinatorics, 21 (2), Paper 2.7, arXiv:1301.1873, Bibcode:2013arXiv1301.1873O, MR 3210641.
  8. ^ Moser, Robin A.; Tardos, Gábor (2010), "A constructive proof of the general Lovász local lemma", Journal of the ACM, 57 (2), Art. 11, arXiv:0903.0544, doi:10.1145/1667053.1667060, MR 2606086.