Dans la complexité de la communication, la conjecture log-rank déclare que
Où est la complexité de communication de M ( x , y ) et r k ( M ) est le rang de M (sous forme de matrice) sur les réels.
Cependant, lorsque vous utilisez simplement la méthode de classement pour réduire la limite vous pouvez utiliser r k sur n'importe quel champ qui vous convient. Pourquoi la conjecture log-rank se limite-t-elle à rk sur les réels? La conjecture est-elle résolue pour r k sur des champs de caractéristique non nulle? Sinon, est-ce intéressant ou y a-t-il quelque chose de spécial à propos de r k sur R ?
cc.complexity-theory
big-picture
linear-algebra
open-problem
communication-complexity
Artem Kaznatcheev
la source
la source
Réponses:
la source