태그 보관물: lower-bounds

lower-bounds

다항식으로 OR 표현 나는 변수 에

나는 변수 에 대한 OR 함수 가 다항식 로 정확하게 표현 될 수 있음을 알고 있습니다 :
이며 .

n

x1,…,xn

p(x1,…,xn)

p(x1,…,xn)=1−∏i=1n(1−xi)

n

그러나

p

가 OR 함수를 정확하게 나타내는 다항식 인 경우 (그래서

∀x∈{0,1}n:p(x)=⋁i=1nxi

) 다음

deg⁡(p)≥n

?



답변

하자 부울 함수이다. 이 다항식 표현되어있는 경우 다음은 multilinear 다항식 표현 갖는다 정도를 : 그냥 전원 교체 , 여기서 의해 x_i로부터 . 따라서 우리는 다 선형 다항식에 대한주의를 제한 할 수 있습니다.

f:{0,1}n→{0,1}

P

Q

deg⁡Q≤deg⁡P

xik

k≥2

xi

주장 : 다항식

{∏i∈Sxi:S⊆[n]}

, 함수

{0,1}n→R

은 공간의 기초를 형성합니다. 모든 함수 중

{0,1}n→R

입니다.

증명 : 먼저 다항식이 선형 적으로 독립적이라는 것을 보여줍니다. 모든 대해 이라고 가정하십시오 . 우리는그 . 모든 대해 이라고 가정하십시오. , 카디널리티 의 집합 가 주어 . 모든 대해 이므로 . 여기서 는 의 좌표에서 입력입니다 . ( x 1 , , x n ) { 0 , 1 } n | S | c S = 0 c T = 0 | T | < k S k T S c T = 0 0 = f ( 1 S

f=∑ScS∏i∈Sxi=0

(x1,…,xn)∈{0,1}n

|S|

cS=0

cT=0

|T|<k

S

k

T⊂S

cT=0

1 S 1 S

0=f(1S)=cS

1S

1

S

 ◻

주장은 함수 의 다중 선 표현 이 고유 하다는 것을 보여줍니다 (실제로 는 값일 필요조차 없습니다 ) . OR의 고유 한 다중 표현은 이며 .F 0 / 1 1 - Π I ( 1 - X I ) N

f:{0,1}n→{0,1}

f

0/1

1−∏i(1−xi)

n

답변

하자 그 모든 다항식하여야 , . 다항식 의 대칭성을 고려하십시오 .
OR 함수는 대칭 부울 함수이므로 , 및 입니다. 이후 의 다항식 비 제로이고, 그것이 갖는 적어도 개의 0, 그 이상의 정도 있어야 . 따라서 도 차수 가져야합니다 .x { 0 , 1 } n p ( x ) = O R ( x ) p q ( k ) = 1

p

x∈{0,1}n

p(x)=OR(x)

p

k=1,2,,nq(k)=1q(0)=0q1nnpn

q(k)=1(nk)∑x:|x|=kp(x).

k=1,2,…,n

q(k)=1

q(0)=0

q−1

n

n

p

n

대칭은 종종 대략적인 부울 함수와 양자 쿼리 복잡성의 연구에 사용됩니다. 예를 들어 http://www.math.uwaterloo.ca/~amchilds/teaching/w11/l19.pdf를 참조하십시오 .


답변

유발과 헨리는이 사실에 대한 두 가지 다른 증거를 제시했습니다. 세 번째 증거가 있습니다.

첫째, Yuval의 답변 에서처럼 우리는 다 선형 다항식에 대한 관심을 제한합니다. 이제 OR 함수와 같은 차수 다선 다항식을 이미 표시했습니다 . 이제 우리가 보여줄 필요는이 다항식이 독특하다는 것입니다. 결과적으로 그 차수는 입니다.

n

n

주장 : 두 개의 다 선형 다항식 p와 q가 하이퍼 큐브에서 같으면 어디에서나 동일합니다.

증명 : r (x) = p (x)-q (x)라고하고, 우리는 모든 x에 대해 r (x) = 0임을 알고 있습니다. r (x)가 동일하게 0임을 보여주고 자합니다. 모순을 향해, 그렇지 않다고 가정하고, 최소도를 갖는 0이 아닌 계수로 r에서 모든 단항을 선택하십시오. 이 monomial 외부의 모든 변수를 0으로 설정하고이 monomial의 모든 변수를 1로 설정하십시오. r (x)는이 입력에서 0이 아니지만이 입력은 부울이므로 모순입니다.

{0,1}n

답변