Гипотеза лог-ранга - Log-rank conjecture

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

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

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

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

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

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

Самый известный верхний предел, сделанный Ловеттом, гласит, что

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

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

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

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

Рекомендации