Na complexidade da comunicação, a conjectura de log-rank afirma que
Onde é a complexidade da comunicação de e é a classificação de (como uma matriz) sobre os reais.M ( x , y ) r k ( M ) M
No entanto, quando você está apenas usando o método de classificação para diminuir o limite pode usar sobre qualquer campo que seja conveniente. Por que a conjectura de log-rank se restringe a rk sobre os reais? A conjectura é resolvida para sobre campos de característica diferente de zero? Caso contrário, é interessante ou há algo especial sobre over ?r k r k r k R
cc.complexity-theory
big-picture
linear-algebra
open-problem
communication-complexity
Artem Kaznatcheev
fonte
fonte
Respostas:
A conjectura falha em . Olhada M ( x , y ) = ⟨ x , y ⟩ mod 2 , e x , y ∈ { 0 , 1 } n . A complexidade da comunicação é Ω ( n ) , mas a classificação de M sobre F 2 é n , pela linearidade do produto interno.F2 M(x,y)=⟨x,y⟩mod2 x,y∈{0,1}n Ω(n) M F2 n
fonte