정보 복잡성은 통신 복잡성에서 매우 유용한 도구로, 주로 분산 문제의 통신 복잡성을 낮추는 데 사용됩니다.
쿼리 복잡성에 대한 정보 복잡성의 유사성이 있습니까? 쿼리 복잡성과 통신 복잡성 간에는 많은 유사점이 있습니다. 종종 (항상 그런 것은 아님) 한 모델의 하한이 다른 모델의 하한으로 변환됩니다. 때때로이 번역은 사소한 것이 아닙니다.
문제의 쿼리 복잡성을 낮추는 데 유용한 정보 복잡성의 개념이 있습니까?
첫 번째 단계는 정보의 복잡성이 그다지 유용하지 않음을 나타냅니다. 예를 들어, 비트 의 OR 계산의 쿼리 복잡도는 무작위 알고리즘의 경우 Ω ( N ) 이고 Ω ( √
엔Ω(엔)
양자 알고리즘의 경우 N ), 정보 복잡성 개념의 가장 간단한 적응은 모든 쿼리 알고리즘에 의해 학습 된 정보가 최대O(logN)임을 나타냅니다(입력에서처음1을볼 때 알고리즘이 중지되기 때문에).
Ω(엔)영형(로그엔)
1
답변
예, 정보 이론은 컴퓨터 과학 문제의 쿼리 복잡성에 대한 하한을 증명하는 데 유용합니다.
Alexander Golynski는 SODA 2009에서 발표 한 “간결한 데이터 구조에 대한 셀 프로브 하한”이라는 제목의 획기적인 논문에서 좋은 예를 제시했습니다. (간결한) 데이터 구조에 대한 비트 프로브 모델. citeseer의 캐시 또는 ACM의 저장소 에서 논문을 다운로드 할 수 있습니다 . 기사의 저널 버전이없는 것 같습니다.
그의 참고 문헌에서 다음 기사에 관심이있을 수도 있습니다.이 정보는 의사 소통의 복잡성과 정보 이론을 관련시킵니다.