布林函數多項式表示法之次方下界

Abstract

以布林函數計算複雜度的研究領域而言，多項式次方是重要的測度。在本論文裡，我們針對受n個變數影響的布林函數，證明數個次方下界限。如果對於所有 x,y\in\{0,1\}^{n}，f(x)\neq f(y) \Rightarrow P(x)\not\equiv P(y) mod(m)成立，則多項式P(x)\in Z_m[x]稱為f(x)佈於Z_m的廣義表示法(generalized representation)}。令m_1與m_2為互質的正整數，而且各自具有s個與t個相異質因數。假設P_1(x)\in Z_{m_1}[x]與P_2(x)\in Z_{m_2}[x]都是對稱(symmetric)多項式，而且同時是某個對稱函數f的廣義表示法，我們證明 m_1m_2\deg(P_1)^s\deg(P_2)^t>n 成立。 如果對於所有x\in\{0,1\}^{n}，f(x)=0 \Leftrightarrow Q(x)\equiv 0 mod(m)成立，則多項式Q(x)\in Z_m[x]稱為f佈於Z_m的單邊表示法(one-sided representation)。則考慮與前述結果相同的條件之下，並令Q(x)與\widetilde{Q}(x)\in Z_{m_2}[x]分別是對稱函數f與\neg f的單邊表示法。我們證明 m_1m_2\deg(P_1)^s\deg(Q)^t>n 與 m_1m_2\deg(P_1)^s\deg(\widetilde{Q})^t>n 至少有一個會成立。請注意Q(x)與\widetilde{Q}(x)可以是非對稱多項式。 接著考慮f(x)是非對稱(non-symmetric)布林函數。令P\in Z_{m_1}[x]是f的一個廣義表示法 ，而且Q(x),\widetilde{Q}(x)\in Z_{m_2}[x]是\neg f的一個單邊表示法。我們證明幾乎必然(almost always) m_1m_2\deg(P_1)^s\deg(Q)^t>\log_2{n}-O(1) 與 m_1m_2\deg(P_1)^s\deg(\widetilde{Q})^t>\log_2{n}-O(1) 至少一個會成立。 假設f與表示法裡出現的n個變數都有關，則稱為非退化(nondegenerate)函數。我們證明針對任何非退化的函數f，都存在一個變數x_i，使得f|_{x_i=0}與f|_{x_i=1}這兩個限制子函數之中，至少有一個仍然與剩下的n-1個變數有關。可以進一步推論得知，針對任何k是1到n-1間的任意整數，存在留有k個自由變數(free variable)的部分賦值(partial assignment) \rho，使得子函數f|_{\rho}與k個變數有關。

Polynomial degree is an important measure for studying the computational complexity of Boolean functions. In this thesis we prove lower bounds for Boolean functions that depend on n variables. A polynomial P(x)\in Z_m[x] is a generalized representation of f(x) over Z_m if \forall x,y\in\{0,1\}^{n}, f(x)\neq f(y) \Rightarrow P(x)\not\equiv P(y) mod(m). Let m_1 and m_2 be relatively prime numbers and have s and t distinct prime factors respectively. If P_1(x)\in Z_{m_1}[x] and P_2(x)\in Z_{m_2}[x] both are symmetric polynomials and are generalized representations for a symmetric function f, we prove m_1m_2\deg(P_1)^s\deg(P_2)^t>n. A polynomial Q(x)\in Z_m[x] is a one-sided representation of f over Z_m if \forall x\in\{0,1\}^{n}, f(x)=0 \Leftrightarrow Q(x)\equiv 0 mod(m). Then with the same conditions as above, and let Q(x),\widetilde{Q}(x)\in Z_{m_2}[x] respectively be one-sided representations of symmetric f and \neg f. We prove at least one of m_1m_2\deg(P_1)^s\deg(Q)^t>n and m_1m_2\deg(P_1)^s\deg(\widetilde{Q})^t>n is true. Note that Q(x) and \widetilde{Q}(x) can be non-symmetric. Next consider a non-symmetric Boolean function f(x). Let P\in Z_{m_1}[x] be a generalized representation, and Q(x),\widetilde{Q}(x)\in Z_{m_2}[x] be one-sided representations for f and \neg f respectively. We prove that almost always at least one of m_1m_2\deg(P_1)^s\deg(Q)^t>\log_2{n}-O(1) and m_1m_2\deg(P_1)^s\deg(\widetilde{Q})^t>\log_2{n}-O(1) is true. A Boolean function f:\{0,1\}^n\to \{0,1\} is called {\em nondegenerate} if f depends on all its n variables. We show that, for any nondegenerate function f, there exists a variable x_i such that at least one of the restrictions f|_{x_i=0} or f|_{x_i=1} must depend on all the remaining n-1 variables. This means for any 1\leq k\leq n-1 there is a partial assignment \rho that leaves k variables free such that the restricted subfunction f|_{\rho} depends on the k variables.