나는 변수 에 대한 OR 함수 가 다항식 로 정확하게 표현 될 수 있음을 알고 있습니다 :
이며 .
그러나
가 OR 함수를 정확하게 나타내는 다항식 인 경우 (그래서
) 다음
?
답변
하자 부울 함수이다. 이 다항식 표현되어있는 경우 다음은 multilinear 다항식 표현 갖는다 정도를 : 그냥 전원 교체 , 여기서 의해 x_i로부터 . 따라서 우리는 다 선형 다항식에 대한주의를 제한 할 수 있습니다.
주장 : 다항식
, 함수
은 공간의 기초를 형성합니다. 모든 함수 중
입니다.
증명 : 먼저 다항식이 선형 적으로 독립적이라는 것을 보여줍니다. 모든 대해 이라고 가정하십시오 . 우리는그 . 모든 대해 이라고 가정하십시오. , 카디널리티 의 집합 가 주어 . 모든 대해 이므로 . 여기서 는 의 좌표에서 입력입니다 . ( 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
1 S 1 S
주장은 함수 의 다중 선 표현 이 고유 하다는 것을 보여줍니다 (실제로 는 값일 필요조차 없습니다 ) . OR의 고유 한 다중 표현은 이며 .F 0 / 1 1 - Π I ( 1 - X I ) N
답변
하자 그 모든 다항식하여야 , . 다항식 의 대칭성을 고려하십시오 .
OR 함수는 대칭 부울 함수이므로 , 및 입니다. 이후 의 다항식 비 제로이고, 그것이 갖는 적어도 개의 0, 그 이상의 정도 있어야 . 따라서 도 차수 가져야합니다 .x ∈ { 0 , 1 } n p ( x ) = O R ( x ) p q ( k ) = 1
k=1,2,…,nq(k)=1q(0)=0q−1nnpn
대칭은 종종 대략적인 부울 함수와 양자 쿼리 복잡성의 연구에 사용됩니다. 예를 들어 http://www.math.uwaterloo.ca/~amchilds/teaching/w11/l19.pdf를 참조하십시오 .
답변
유발과 헨리는이 사실에 대한 두 가지 다른 증거를 제시했습니다. 세 번째 증거가 있습니다.
첫째, Yuval의 답변 에서처럼 우리는 다 선형 다항식에 대한 관심을 제한합니다. 이제 OR 함수와 같은 차수 다선 다항식을 이미 표시했습니다 . 이제 우리가 보여줄 필요는이 다항식이 독특하다는 것입니다. 결과적으로 그 차수는 입니다.
주장 : 두 개의 다 선형 다항식 p와 q가 하이퍼 큐브에서 같으면 어디에서나 동일합니다.
증명 : r (x) = p (x)-q (x)라고하고, 우리는 모든 x에 대해 r (x) = 0임을 알고 있습니다. r (x)가 동일하게 0임을 보여주고 자합니다. 모순을 향해, 그렇지 않다고 가정하고, 최소도를 갖는 0이 아닌 계수로 r에서 모든 단항을 선택하십시오. 이 monomial 외부의 모든 변수를 0으로 설정하고이 monomial의 모든 변수를 1로 설정하십시오. r (x)는이 입력에서 0이 아니지만이 입력은 부울이므로 모순입니다.