Я знаю, что тривиально функция OR для переменных может быть точно представлена полиномом следующим образом: , который имеет степень .х 1 , ... , х п р ( х 1 , ... , х п ) р ( х 1 , ... , х п ) = 1 - П п я = 1 ( 1 - х я ) п
Но как я могу показать, что кажется очевидным, что если - это многочлен, который точно представляет функцию OR (поэтому ), то ?
Ответы:
Пусть - булева функция. Если оно имеет полиномиальное представление P, то оно имеет полилинейное полиномиальное представление Q степени deg Q ≤ deg P : просто замените любую степень x k i , где k ≥ 2 , на x i . Таким образом, мы можем ограничить наше внимание полилинейными полиномами.f:{0,1}n→{0,1} P Q degQ≤degP xki k≥2 xi
Утверждение: Полиномы , как функции { 0 , 1 } п → R образуют базис для пространства всех функций { 0 , 1 } п → R .{∏i∈Sxi:S⊆[n]} {0,1}n→R {0,1}n→R
Доказательство. Сначала покажем, что полиномы линейно независимы. Предположим, что для всех ( x 1 , … , x n ) ∈ { 0 , 1 } n . Докажем (сильной) индукцией по | S | что с S = 0 . Предположим, что c T = 0 для всех | Tf=∑ScS∏i∈Sxi=0 (x1,…,xn)∈{0,1}n |S| cS=0 cT=0 , и давайте дадим множество S мощности k . Для всех T ⊂ S мы знаем по индукциичто с Т = 0 и т 0 = F ( 1 S ) = гр S , где 1 S является входомкоторый является 1 по координатам S .|T|<k S k T⊂S cT=0 0=f(1S)=cS 1S 1 S □
Утверждение показывает, что полилинейное представление функции является уникальным (действительно, f даже не должно быть 0 / 1- значным). Единственное мультилинейное представление OR - это 1 - ∏ i ( 1 - x i ) , имеющее степень n .е: { 0 , 1 }N→ { 0 , 1 } е 0 / 1 1 - ∏я( 1 - хя) N
источник
Пусть - такой многочлен, что для всех x ∈ { 0 , 1 } n , p ( x ) = O R ( x ) . Рассмотрим симметризацию многочлена p : q ( k ) = 1п x ∈ { 0 , 1 }N p ( x ) = O R ( x ) п Обратите внимание, что, поскольку функция OR является симметричной булевой функцией, мы имеем ее дляk=1,2,…,n,q(k)=1иq(0)=0. Посколькуq-1- ненулевой многочлен, и он имеет по крайней мереn0, он должен иметь степень по крайней мереn. Следовательно,
Симметризация часто используется при изучении приближенной степени булевых функций и сложности квантовых запросов. См., Например, http://www.math.uwaterloo.ca/~amchilds/teaching/w11/l19.pdf .
источник
Юваль и Генри дали два разных доказательства этого факта. Вот третье доказательство.
Во-первых, как и в ответе Ювала, мы ограничиваем наше внимание полилинейными полиномами. Теперь вы уже продемонстрировали полилинейный полином степени , равный функции OR. Теперь все, что нам нужно показать, - это то, что этот многочлен является уникальным, и, следовательно, вы нашли одно-единственное представление функции OR как многочлена. Следовательно, его степень равна n .N N
Утверждение: если два гиперлинейных полинома p и q равны на гиперкубе, то они везде одинаковы.
Доказательство. Пусть r (x) = p (x) - q (x), и мы знаем, что r (x) = 0 для всех x в . Мы хотим показать, что r (x) тождественно равен нулю. Для противоречия предположим, что это не так, и выберите любой моном в r с ненулевым коэффициентом, который имеет минимальную степень. Установите все переменные вне этого монома равными 0, а все переменные в этом мономе равными 1. На этом входе r (x) отлично от нуля, но этот вход является логическим, что противоречит.{ 0 , 1 }N
источник