Пусть быть мульти-мерный полином с коэффициентами над полем . Мультилинеаризация , обозначаемая , является результатом многократной замены каждого с на . Результат, очевидно, является полилинейным полиномом.р ( х 1 , ... , х п ) F р р х д я д > 1 х I
Рассмотрим следующую проблему: для заданной арифметической схемы над и заданных элементов поля , compute .С ( х 1 , ... , х п ) Р 1 , ... , а п C ( 1 , ... , п )
Вопрос: Предполагая, что арифметика поля может быть сделана в единицу времени, есть ли алгоритм полиномиального времени для этого? Добавлено позже: меня также будет интересовать особый случай, когда на самом деле является формулой (схема разветвления ).C 1
cc.complexity-theory
polynomials
slimton
источник
источник
Ответы:
В случае, если поле F имеет размер не менее 2 n , я думаю, что эта проблема сложная. Более конкретно, я думаю, что если вышеупомянутое может быть эффективно решено для F такого большого размера, то CNF-SAT имеет эффективные рандомизированные алгоритмы. Скажем, нам дана формула CNF φ . Можно легко придумать арифметическую схему C, которая вычисляет «арифметизацию» p из φ , где многочлен p согласуется с формулой φ на 0 - 1 входах. Рассмотрим мультилинеаризацию q от p . Обратите внимание, что дF 2n F φ C p φ p φ 0 1 q p q согласуется с p и, следовательно, φ на { 0 , 1 } n .p φ {0,1}n
Я утверждаю, что q ненулевое, если φ выполнимо. Ясно, что если q = 0 , то φ не может быть удовлетворена. Для обратного можно показать, что любой ненулевой полилинейный полином не может обращаться в нуль на всех { 0 , 1 } n . Это означает, что ненулевой q (и, следовательно, соответствующий φ ) не обращается в нуль на некотором входе в { 0 , 1 } n .q φ q=0 φ {0,1}n q φ {0,1}n
Следовательно, проверка выполнимости φ эквивалентна проверке, является ли q ненулевым. Скажем, теперь, что мы могли бы оценить д над большим полем F . Затем, используя лемму Шварца-Циппеля, мы могли бы проверить тождество q, используя эффективный рандомизированный алгоритм, и проверить, является ли он нулевым полиномом (размер F используется для верхней оценки ошибки в лемме Шварца-Циппеля).φ q q F q F
источник
Предположим, что существует алгоритм поли-времени, в котором C ( → x ) ∈ F ( → x ) и → a вычислили результат мультилинеаризации C на → a . (без потери общности , я буду считать , что выход → B будет вектором р -разрядного двоичных чисел б я это к тогда и только тогда б я , к являюсь одним.)C(x⃗ )∈F(x⃗ ) a⃗ C a⃗ b⃗ p bi k bi,k
Поскольку P ⊆ P / p o l y , существует логическая схема с полизайзером, которая задает кодирование арифметической схемы, а значения переменных вычисляют мультилинеаризацию арифметической схемы на входах. Пусть называют эту схему M .P⊆P/poly M
Пусть C - произвольная арифметическая схема. Зафиксируем переменные булевой схемы M, которые описывают арифметическую схему, поэтому у нас есть булева схема, вычисляющая мультилинеаризацию C на заданных входах.C M C
Мы можем превратить эту схему в арифметическую схему над F p , отметив, что x p - 1 равно 1 для всех значений, но 0, поэтому сначала увеличьте все входы до мощности p - 1 . Замените все ворота f ∧ g умножением f . g , каждый f ∨ g ворот на f + g - f . г и каждый ¬ е ворота на 1 - е .Fp xp−1 1 0 p−1 f∧g f.g f∨g f+g−f.g ¬f 1−f
В предположении, которое мы сделали выше относительно формата вывода, мы можем превратить вывод из двоичного значения в значения, превышающие F p . Возьмите выходные данные для b i и объедините их, чтобы получить ∑ 0 ≤ k ≤ p - 1 k b i , k .Fp bi ∑0≤k≤p−1kbi,k
Мы также можем преобразовать входные данные, заданные в виде значений над F p, в двоичную форму, поскольку полиномы проходят через любое конечное число точек. Например, если мы работаем в моде 3 , рассмотрим многочлены 2 x ( x + 1 ) и 2 x ( x + 2 ), которые дают первый и второй биты ввода x ∈ F 3 .Fp mod3 2x(x+1) 2x(x+2) x∈F3
Объединение этих мы имеем арифметическую схему над F р вычислительного мульти-линеаризацию C с размером polynomail в размере C .Fp C C
источник