Почему гипотеза лог-ранга использует ранг над реалами?

В сложности связи гипотеза лог-ранга утверждает, что

c c (M) = (\log r k (M))^{O (1)}

$cc(M) = (\log rk(M))^{O(1)}$

Где - сложность связи а - ранг (в виде матрицы) над реалами. $cc(M)$ $M(x,y)$ $rk(M)$ $M$

Однако, когда вы просто используете метод ранга для понижения границы вы можете использовать любого удобного поля. Почему гипотеза о логарифмическом ограничении ограничена реальными значениями? Разрешена ли гипотеза для над полями ненулевой характеристики? Если нет, то это интересно или есть что-то особенное в over ? $cc(M)$ $rk$ $rk$ $rk$ $\mathbb{R}$

cc.complexity-theory big-picture linear-algebra open-problem communication-complexity Артем Казнатчеев
источник

Кстати, я считаю, что вы должны ограничить двоичным, иначе вы можете составить тривиальные контрпримеры.

M

$M$

Сашо Николов

@SashoNikolov Что вы подразумеваете под тривиальными контрпримерами, если не равно (я полагаю, вы имеете в виду реал)?

M

$M$

0 / 1

$0/1$

T ....

Например, проблема «угадай мое число», т.е. у Алисы есть число в и Боб должен его вывести. Легко видеть, что сложность связи равна но ранг матрицы равен .

{1, \dots, N}

$\{1, \ldots, N\}$

\log N

$\log N$

1

$1$

Сашо Николов

@SashoNikolov Можете ли вы определить, угадать мой номер точно? Я не могу визуализировать характерную матрицу. У Алисы есть а у Боба есть , тогда что такое функция из которой определяется ранга ?

x

$x$

y

$y$

f (x, y)

$f(x,y)$

M

$M$

1

$1$

T ....

Функция где и - битные векторы. Если определение сложности связи требует, чтобы значение было полностью определено протоколом протокола (это определение в Kushilevitz-Nisan), то ясно, что сложность равна .

f (x, y) = x

$f(x, y) = x$

x

$x$

y

$y$

n

$n$

f

$f$

n

$n$

Сашо Николов

Почему гипотеза лог-ранга использует ранг над реалами?

Ответы: