Гипотеза о логранге

В теоретической информатике гипотеза о лог-ранге утверждает, что детерминированная сложность связи двусторонней булевой функции полиномиально связана с логарифмом ранга ее входной матрицы.

Позволять $D(f)$ обозначают детерминированную коммуникационную сложность функции и пусть $\operatorname {rank} (f)$ обозначим ранг ее входной матрицы $M_{f}$ (по сравнению с реальными). Поскольку каждый протокол использует до $c$ битовые разделы $M_{f}$ в самое большее $2^{c}$ одноцветные прямоугольники, каждый из которых имеет ранг не более 1,

$D(f)\geq \log _{2}\operatorname {rank} (f).$

Гипотеза о логранге утверждает, что $D(f)$ также ограничен сверху полиномом логранга: для некоторой константы $C$,

$D(f)=O((\log \operatorname {rank} (f))^{C}).$

Ловетт доказал верхнюю оценку

$D(f)=O\left({\sqrt {\operatorname {rank} (f)}}\log \operatorname {rank} (f)\right).$

Это усовершенствовали Судаков и Томон, который удалил логарифмический множитель, показав, что

$D(f)=O\left({\sqrt {\operatorname {rank} (f)}}\right).$

Это лучшая известная на данный момент верхняя граница.

Самая известная нижняя граница, предложенная Гёосом, Питасси и Ватсоном, заявляет, что $C\geq 2$. Другими словами, существует последовательность функций $f_{n}$, логранг которого стремится к бесконечности, такой, что

$D(f_{n})={\tilde {\Omega }}((\log \operatorname {rank} (f_{n}))^{2}).$

В 2019 году приблизительная версия гипотезы была опровергнута.

См. также

• Список нерешенных проблем информатики