Гипотеза логарифмического ранга

Нерешенная проблема в информатике :. Докажите или опровергните гипотезу логарифмического ранга. (другие нерешенные проблемы в информатике)

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

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

$D\; (f)\; \ge \; log\; 2\; \; rank\; \; (f).\; \{\backslash \; displaystyle\; D\; (f)\; \backslash \; geq\; \backslash \; log\; \_\; \{2\}\; \backslash \; operatorname\; \{rank\}\; (f).\}$

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

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

Самая известная верхняя граница, полученная Ловеттом, гласит, что

$D\; (f)\; =\; O\; (ранг\; \; (f)\; журнал\; \; ранг\; \; (f)).\; \{\backslash \; displaystyle\; D\; (f)\; =\; O\; \backslash \; left\; (\{\backslash \; sqrt\; \{\backslash \; operatorname\; \{rank\}\; (f)\}\}\; \backslash \; log\; \backslash \; operatorname\; \{rank\}\; (f)\; \backslash \; right).\}$

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

$D\; (fn)\; =\; \Omega \; ~\; (\; (журнал\; \; ранг\; \; (fn))\; 2).\; \{\backslash \; displaystyle\; D\; (f\_\; \{n\})\; =\; \{\backslash \; tilde\; \{\backslash \; Omega\}\}\; ((\backslash \; log\; \backslash \; operatorname\; \{rank\}\; (f\_\; \{n\}))\; ^\; \{2\}).\}$

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