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

以布林函數計算複雜度的研究領域而言，多項式次方是重要的測度。在本論文裡，我們針對受n個變數影響的布林函數，證明數個次方下界限。如果對於所有 x,yin{0,1}^{n}，f(x) eq f(y) Rightarrow P(x) otequiv 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_2deg(P_1)^sdeg(P_2)^t>n 成立。如果對於所有xin{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與 eg f的單邊表示法。我們證明 m_1m_2deg(P_1)^sdeg(Q)^t>n 與 m_1m_2deg(P_1)^sdeg(widetilde{Q})^t>n 至少有一個會成立。請注意Q(x)與widetilde{Q}(x)可以是非對稱多項式。接著考慮f(x)是非對稱(non-symmetric)布林函數。令Pin Z_{m_1}[x]是f的一個廣義表示法，而且Q(x),widetilde{Q}(x)in Z_{m_2}[x]是 eg f的一個單邊表示法。我們證明幾乎必然(almost always) m_1m_2deg(P_1)^sdeg(Q)^t>log_2{n}-O(1) 與 m_1m_2deg(P_1)^sdeg(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) ho，使得子函數f|_{ ho}與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,yin{0,1}^{n}, f(x) eq f(y) Rightarrow P(x) otequiv 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_2deg(P_1)^sdeg(P_2)^t>n. A polynomial Q(x)in Z_m[x] is a one-sided representation of f over Z_m if forall xin{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 eg f. We prove at least one of m_1m_2deg(P_1)^sdeg(Q)^t>n and m_1m_2deg(P_1)^sdeg(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 Pin 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 eg f respectively. We prove that almost always at least one of m_1m_2deg(P_1)^sdeg(Q)^t>log_2{n}-O(1) and m_1m_2deg(P_1)^sdeg(widetilde{Q})^t>log_2{n}-O(1) is true. A Boolean function f:{0,1}^n o {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 1leq kleq n-1 there is a partial assignment ho that leaves k variables free such that the restricted subfunction f|_{ ho} depends on the k variables.

並列關鍵字

degree lower bound ； multilinear polynomial representation ； polynomial modulo composite ； Boolean function complexity ； restriction (partial assignments) method

參考文獻

[43] S. C. Tsai, and M. C. Yang, ”Representing Symmetric Boolean Functions with Polynomial over Composite Moduli,” Journal of Information Science and Engineering, to appear.

[4] N. Alon and J.H. Spencer. The Probabilistic Method, third edition. John Wiley and Sons, 2008.

[16] D. Z. Du and F. K. Hwang, Combinatorial group testing and its application, 2nd ed. World Scientifi c Publishing, 2000.

[1] S. Aaronson, ”The Polynomial Method in Quantum and Classical Computing,” IEEE 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2008.

[2] N. Alon and R. Beigel. ”Lower bounds for approximations by low degree polynomials over Zm,” Proceedings of the 16th IEEE Conference on Computational Complexity (CCC), 2001.

國際替代計量

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

全文下載

主題瀏覽