Оценивая мультилинеаризацию арифметической схемы?

13

Пусть быть мульти-мерный полином с коэффициентами над полем . Мультилинеаризация , обозначаемая , является результатом многократной замены каждого с на . Результат, очевидно, является полилинейным полиномом.р ( х 1 , ... , х п ) F р р х д я д > 1 х Ip(x1,,xn)Fpp^xdid>1xi

Рассмотрим следующую проблему: для заданной арифметической схемы над и заданных элементов поля , compute .С ( х 1 , ... , х п ) Р 1 , ... , а п C ( 1 , ... , п )C(x1,,xn)Fa1,,anC^(a1,,an)

Вопрос: Предполагая, что арифметика поля может быть сделана в единицу времени, есть ли алгоритм полиномиального времени для этого? Добавлено позже: меня также будет интересовать особый случай, когда на самом деле является формулой (схема разветвления ).C 1C1

slimton
источник
1
Почему это было бы эквивалентно вычислению выхода замкнутой цепи? Проблема, с которой я сталкиваюсь, состоит в том, что схема может иметь непересекающиеся пути от входа к нескольким внутренним узлам умножения, и для оценки каждого из этих внутренних узлов умножения потребуется заменить на в одном пути и на в другом. В схеме с экспоненциальным числом путей это выглядит так, как будто существует экспоненциальное число случаев, о которых нужно позаботиться. x i x i a i 1xixiai1
Слитон
2
@Kaveh: я не понимаю Посмотрите на схему . Если вы просто замените узел ввода на узел со значением и оцените стандартным способом, то в итоге вы получите вместо . Модель вычисления: просто нормальное полиномиальное время на машинах Тьюринга. Думайте о поле как о для конкретности, если хотите. ( x x ) x a a 2 a Z / 3 Z(xx)xaa2aZ/3Z
Slimton
2
@Kaveh: Я не понимаю, как такой алгоритм подразумевает то, что вы говорите, но это действительно противоречит общей гипотезе сложности арифметической схемы: у Перманента нет многоразмерных арифметических схем (над полями, отличными от F_2). Рассмотрим многочлен р = Π я ( Σ J х я J у J )p=i(jxijyj) . Полилинейная часть qq этого многочлена обладает свойством того, что его наивысшая степень ( = 2 n=2n ) является просто r = y 1 y 2y n P e r ( x11 ,, x n n )r=y1y2ynPer(x11,,xnn). Если есть небольшая арифметическая схема, вычисляющаяqq, то можно показать, что есть небольшая арифметическая схема, вычисляющаяrr.
Srikanth
1
@Srikanth: я не видел ваш комментарий до публикации моего ответа (который оказался той же конструкцией, которую вы дали в своем комментарии). С тех пор я удалил свой ответ, и вы должны опубликовать свой комментарий в качестве ответа.
Джошуа Грохов
2
@ Джошуа: я не добавил свой комментарий в качестве ответа, так как я не понимаю, почему строительные работы Каве. Я вижу, что арифметическая схема вычисляет многочлен, который согласуется с мультилинеаризацией на всех входах, но я не уверен, что он формально вычисляет мультилинеаризацию данного многочлена (см. Мои комментарии после ответа Каве). Моя конструкция (и ваша) предполагает, что мультилинеаризация вычисляется формально.
Срикант

Ответы:

12

В случае, если поле F имеет размер не менее 2 n , я думаю, что эта проблема сложная. Более конкретно, я думаю, что если вышеупомянутое может быть эффективно решено для F такого большого размера, то CNF-SAT имеет эффективные рандомизированные алгоритмы. Скажем, нам дана формула CNF φ . Можно легко придумать арифметическую схему C, которая вычисляет «арифметизацию» p из φ , где многочлен p согласуется с формулой φ на 0 - 1 входах. Рассмотрим мультилинеаризацию q от p . Обратите внимание, что дF2nFφCpφpφ01qpqсогласуется с p и, следовательно, φ на { 0 , 1 } n .pφ{0,1}n

Я утверждаю, что q ненулевое, если φ выполнимо. Ясно, что если q = 0 , то φ не может быть удовлетворена. Для обратного можно показать, что любой ненулевой полилинейный полином не может обращаться в нуль на всех { 0 , 1 } n . Это означает, что ненулевой q (и, следовательно, соответствующий φ ) не обращается в нуль на некотором входе в { 0 , 1 } n .qφq=0φ{0,1}nqφ{0,1}n

Следовательно, проверка выполнимости φ эквивалентна проверке, является ли q ненулевым. Скажем, теперь, что мы могли бы оценить д над большим полем F . Затем, используя лемму Шварца-Циппеля, мы могли бы проверить тождество q, используя эффективный рандомизированный алгоритм, и проверить, является ли он нулевым полиномом (размер F используется для верхней оценки ошибки в лемме Шварца-Циппеля).φqqFqF

Srikanth
источник
Мне кажется, что F - фиксированное поле, потому что во входных данных нет ничего, что бы указывало на F. Также обратите внимание, что этот вопрос предполагает, что полевые операции занимают единичное время.
Каве
Спасибо, Срикант. Как и предполагал Каве, меня действительно интересовал случай фиксированного конечного поля, но этот ответ, который вы дали, помогает мне немного лучше понять вопрос.
Слитон
3

Предположим, что существует алгоритм поли-времени, в котором C ( x ) F ( x ) и a вычислили результат мультилинеаризации C на a . (без потери общности , я буду считать , что выход B будет вектором р -разрядного двоичных чисел б я это к тогда и только тогда б я , к являюсь одним.)C(x⃗ )F(x⃗ )a⃗ Ca⃗ b⃗ pbikbi,k

Поскольку P P / p o l y , существует логическая схема с полизайзером, которая задает кодирование арифметической схемы, а значения переменных вычисляют мультилинеаризацию арифметической схемы на входах. Пусть называют эту схему M .PP/polyM

Пусть C - произвольная арифметическая схема. Зафиксируем переменные булевой схемы M, которые описывают арифметическую схему, поэтому у нас есть булева схема, вычисляющая мультилинеаризацию C на заданных входах.CMC

Мы можем превратить эту схему в арифметическую схему над F p , отметив, что x p - 1 равно 1 для всех значений, но 0, поэтому сначала увеличьте все входы до мощности p - 1 . Замените все ворота f g умножением f . g , каждый f g ворот на f + g - f . г и каждый ¬ е ворота на 1 - е .Fpxp110p1fgf.gfgf+gf.g¬f1f

В предположении, которое мы сделали выше относительно формата вывода, мы можем превратить вывод из двоичного значения в значения, превышающие F p . Возьмите выходные данные для b i и объедините их, чтобы получить 0 k p - 1 k b i , k .Fpbi0kp1kbi,k

Мы также можем преобразовать входные данные, заданные в виде значений над F p, в двоичную форму, поскольку полиномы проходят через любое конечное число точек. Например, если мы работаем в моде 3 , рассмотрим многочлены 2 x ( x + 1 ) и 2 x ( x + 2 ), которые дают первый и второй биты ввода x F 3 .Fpmod32x(x+1)2x(x+2)xF3

Объединение этих мы имеем арифметическую схему над F р вычислительного мульти-линеаризацию C с размером polynomail в размере C .FpCC

Кава
источник
2
Мне не ясно, почему арифметическая схема, которую вы описали, вычисляет полилинеаризацию C или даже полилинейный полином. Я могу только видеть, что арифметическая схема вычисляет некоторый многочлен, который согласуется с мультилинеаризацией C на 0 - 1 входах. CC01
Срикант
@Srikanth: арифметическая версия логической схемы M (с фиксированными входами) вычисляет полилинейную версию C , она не обязательно должна быть мультилинейной. Тогда единственная проблема заключается в том, что вход / выход находятся в двоичном формате, а не в значениях, превышающих F p , поэтому мне просто нужно исправить кодировку для ввода / вывода из двоичного в исходные значения ввода и вывода. Результирующая схема представляет собой арифметическую схему, которая получает значения для переменных C , кодирует их в двоичном формате, вычисляет значение мультилинейности C по этим входам и выводит ответ в двоичном виде, а затем переводит их обратно в F p .
Каве
[продолжение] В результате это арифметическая схема с тем же переменным , что С имеет, и с такими же выходами, и это вычисление multilinearization из C .
Каве
2
@Kaveh: Вы предполагали, что вход в логическую схему M имеет ту же форму, что и выход M ? В любом случае, я до сих пор не убежден. Для арифметической схемы вполне возможно вычислить многочлен f, который согласуется с многочленом g на всех входах поля, но при этом f g . Например, многочлен x p согласуется с x на всех входах, и все же они не равны как многочлены. Откуда вы знаете, что схема M не просто вычисляет немультилинейный полином, который согласуется с мультилинейностью C на всех входах?
Srikanth
@Srikanth: I have described the form of input and output in my answer. The input to M is in binary, the output of M is in the form stated above. I haven't said that it is multilinear, I have only said that it computes the multilinearization of the C.
Kaveh