Информационная сложность была очень полезным инструментом в сложности коммуникации, в основном используемой для снижения сложности коммуникации в распределенных задачах.
Есть ли аналог сложности информации для сложности запросов? Существует много параллелей между сложностью запросов и сложностью коммуникации; часто (но не всегда!) нижняя граница в одной модели переводится в нижнюю границу в другой модели. Иногда этот перевод довольно нетривиален.
Существует ли понятие сложности информации, которое полезно для более низкого ограничения сложности задач?
Первый проход указывает на то, что сложность информации не очень полезна; например, сложность запроса вычисления ИЛИ из битов равна для рандомизированных алгоритмов и Ω ( √для квантовых алгоритмов, тогда как наиболее простая адаптация понятия информационной сложности указывает на то, что информация, полученная любым алгоритмом запроса, не превышаетO(logN)(потому что алгоритм останавливается, когда видит первую1во входных данных).