Представление ИЛИ с полиномами

23

Я знаю, что тривиально функция OR для переменных может быть точно представлена ​​полиномом следующим образом: , который имеет степень .х 1 , ... , х п р ( х 1 , ... , х п ) р ( х 1 , ... , х п ) = 1 - П п я = 1 ( 1 - х я ) пnx1,,xnp(x1,,xn)p(x1,,xn)=1i=1n(1xi)n

Но как я могу показать, что кажется очевидным, что если - это многочлен, который точно представляет функцию OR (поэтому ), то ?px{0,1}n:p(x)=i=1nxideg(p)n

matthon
источник
1
Вы говорите о реальных полиномах? Или полиномы по модулю 2? Если вы хотите поговорить о модуле 6 (или других составных числах), то вопрос становится более интересным.
Игорь Шинкарь

Ответы:

30

Пусть - булева функция. Если оно имеет полиномиальное представление P, то оно имеет полилинейное полиномиальное представление Q степени deg Q deg P : просто замените любую степень x k i , где k 2 , на x i . Таким образом, мы можем ограничить наше внимание полилинейными полиномами.f:{0,1}n{0,1}PQdegQdegPxikk2xi

Утверждение: Полиномы , как функции { 0 , 1 } пR образуют базис для пространства всех функций { 0 , 1 } пR .{iSxi:S[n]}{0,1}nR{0,1}nR

Доказательство. Сначала покажем, что полиномы линейно независимы. Предположим, что для всех ( x 1 , , x n ) { 0 , 1 } n . Докажем (сильной) индукцией по | S | что с S = 0 . Предположим, что c T = 0 для всех | Tf=ScSiSxi=0(x1,,xn){0,1}n|S|cS=0cT=0 , и давайте дадим множество S мощности k . Для всех T S мы знаем по индукциичто с Т = 0 и т 0 = F ( 1 S ) = гр S , где 1 S является входомкоторый является 1 по координатам S .|T|<kSkTScT=00=f(1S)=cS1S1S 

Утверждение показывает, что полилинейное представление функции является уникальным (действительно, f даже не должно быть 0 / 1- значным). Единственное мультилинейное представление OR - это 1 - i ( 1 - x i ) , имеющее степень n .f:{0,1}n{0,1}f0/11i(1xi)n

Юваль Фильмус
источник
26

Пусть - такой многочлен, что для всех x { 0 , 1 } n , p ( x ) = O R ( x ) . Рассмотрим симметризацию многочлена p : q ( k ) = 1пИкс{0,1}Nп(Икс)знак равноОр(Икс)пОбратите внимание, что, поскольку функция OR является симметричной булевой функцией, мы имеем ее дляk=1,2,,n,q(k)=1иq(0)=0. Посколькуq-1- ненулевой многочлен, и он имеет по крайней мереn0, он должен иметь степень по крайней мереn. Следовательно,

Q(К)знак равно1(NК)ΣИкс:|Икс|знак равноКп(Икс),
Кзнак равно1,2,...,NQ(К)знак равно1Q(0)знак равно0Q-1NN также должен иметь степень n .пN

Симметризация часто используется при изучении приближенной степени булевых функций и сложности квантовых запросов. См., Например, http://www.math.uwaterloo.ca/~amchilds/teaching/w11/l19.pdf .

Генри Юн
источник
Мне кажется, что для того, чтобы ваше доказательство сработало, вам нужно показать, что степень q не больше степени p. Это мне не понятно. Как вы это показываете?
Матф
Пусть d = deg (p). Тогда q является суммой полиномов степени d, следовательно, степень q не больше d.
Генри Юн
3

Юваль и Генри дали два разных доказательства этого факта. Вот третье доказательство.

Во-первых, как и в ответе Ювала, мы ограничиваем наше внимание полилинейными полиномами. Теперь вы уже продемонстрировали полилинейный полином степени , равный функции OR. Теперь все, что нам нужно показать, - это то, что этот многочлен является уникальным, и, следовательно, вы нашли одно-единственное представление функции OR как многочлена. Следовательно, его степень равна n .NN

Утверждение: если два гиперлинейных полинома p и q равны на гиперкубе, то они везде одинаковы.

Доказательство. Пусть r (x) = p (x) - q (x), и мы знаем, что r (x) = 0 для всех x в . Мы хотим показать, что r (x) тождественно равен нулю. Для противоречия предположим, что это не так, и выберите любой моном в r с ненулевым коэффициентом, который имеет минимальную степень. Установите все переменные вне этого монома равными 0, а все переменные в этом мономе равными 1. На этом входе r (x) отлично от нуля, но этот вход является логическим, что противоречит.{0,1}N

Робин Котари
источник