Объяснить тензорную интерпретацию Гурвица статьи Деолаликара

20

[Примечание: я полагаю, что этот вопрос никоим образом не зависит от правильности или неправильности статьи Деолаликара.]

В блоге Скотта Ааронсона « Оптимизированный Штетл» в дискуссии о недавней попытке Деолаликара на P против NP Леонид Гурвиц сделал следующий комментарий :

Я попытался понять / переформулировать подход, и вот моя, возможно, очень минималистская, попытка: дискретные вероятностные распределения в статье можно рассматривать как тензоры или очень специальные полилинейные полиномы. Предположение «P = NP» каким-то образом дает (полином?) Верхнюю границу тензорного ранга. И, наконец, используя известные вероятностные результаты, он получает несопоставимую (экспоненциальную?) Нижнюю границу для того же ранга. Если я прав, то этот подход очень умный, в хорошем смысле элементарный, способ подтолкнуть предыдущие алгебро-геометрические подходы.

Несмотря на подозреваемые / известные недостатки в доказательстве Деолаликара, мне любопытно:

Каким образом распределения, обсуждаемые в статье Деолаликара, могут рассматриваться как тензоры, и как утверждения его результатов (независимо от их правильности) переводятся в утверждения о тензорном ранге?

Джошуа Грохов
источник
Просто видел это. Почему бы не спросить самого Гурвица? ...
Райан Уильямс
1
@ Райан: я сделал :). Он быстро ответил, что сейчас занят, но в конце концов обязательно доберется до него. Это было какое-то время, и я надеялся, что кто-то здесь сможет объяснить это замечание быстрее.
Джошуа Грохов

Ответы:

10

[Я читал что-то, что, по моему мнению, было совершенно не связано, а затем у меня был «ага момент», так что я думаю, что я нашел хотя бы часть ответа. Я не уверен, что именно это имел в виду Гурвиц, но для меня это имеет смысл.]

Распределение по п двоичных переменных можно рассматривать как элемент тензорного произведения R 2R 2 (n факторов) (на самом деле это ассоциированное проективное пространство, но мы вернемся к этому). Если мы помечаем базовые элементы каждой копии R 2 с помощью | 0 и | 1 x1,...,xnR2R2R2|0|1тогда базис этого тензорного пространства произведений задается множеством всех n-битных строк. Если у нас есть элемент этого тензорного произведения, коэффициенты которого составляют 1, то мы можем интерпретировать коэффициент любой заданной n-битной строки как вероятность появления этой строки - отсюда распределение вероятности! Теперь, поскольку нам нужны только распределения вероятностей (коэффициенты, суммирующие 1), мы можем нормализовать любой вектор в тензорном произведении, чтобы иметь это свойство. Рассматривая только нормированные тензоры, мы действительно рассматриваем только элементы проективного пространства этого тензорного произведения.

Теперь мы должны связать тензорный ранг с понятием Деолаликара о полилоге параметризуемости. В соответствии с этой страницей Терри Тао, кажется , что понятие Deolalikar о Полилог-parametrizability является то , что распределение может быть «учтено потенциалами» , как ц ( х 1 , . . . , Х п ) = Π п я = 1 р I ( x i ; x p a ( i ) ) где pa (i) - набор переменных polylog (n), определенных как «родители i», иμμ(x1,...,xn)=i=1npi(xi;xpa(i)) - это распределение по x i, которое зависит только от этих родительских переменных. Причем ориентированный граф родителей должен быть ациклическим.pi(;xpa(i))xi

Давайте начнем с очень простого вида распространения. Пусть удовлетворяет μ ( х 1 , . . . , Х п ) = Π п я = 1 р я ( х я ) для некоторых распределений р я (где р я завишу только от й я ). Тогда , надеюсь , понятно , что соответствующий тензор ранг 1 тензор: ( р 1 ( 0 ) | 0 +μμ(x1,...,xn)=i=1npi(xi)pipixi .(p1(0)|0+p1(1)|1)(pn(0)|0+pn(1)|1)

Для немного более сложного распределения предположим, что мы хотим рассмотреть равномерное распределение по строкам, где (они являются отрицанием друг друга) для всех i . В трактовке Дао языка Деолаликара это будет O ( 1 ) -параметризуемое распределение. Тогда это соответствует тензором ( | 0 | 1 + | 1 | 0 ) x2i=1x2i+1iO(1) (должно быть нормализованы). Если мы выпишем это полностью, он содержит 2 n / 2 слагаемых и, следовательно, имеет тензорный ранг не более 2 n / 2 над R 2 . Однако над R 2R 2 он имеет тензорный ранг 1! Я полагаю, что последний факт соответствует факту, что факторизация может быть описана O ( n ) числами - O(|0|1+|1|0)(|0|1+|1|0)2n/22n/2R2R2R2O(n) для каждой пары соседних битов, для каждой из O ( n ) соседних пар. Значительно меньше, чем 2 n действительных чисел, требуемых в теории для произвольного распределения mu на булевом кубе.O(1)O(n)2n

У меня все еще проблемы с формулировкой двух вопросов, и я буду признателен за дальнейшие ответы на них:

  • Уточнение последнего соответствия
  • Выписать формулы для тензора, соответствующего параметрическому параметру полилога, и получить верхнюю оценку его ранга.
Джошуа Грохов
источник
ты когда-нибудь возвращался к этому?
T ....