以多項式表示布林函數的最小次方下限問題

Abstract

本計劃目標是針對布林函數(Boolean function)的多項式表示法，探討其次方 (degree)下界。用多項式來表示布林函數是少數已知可供證明電路複雜度(circuit complexity)的途徑之一，電路複雜度牽涉許多計算機科學基礎且未解的重要問題；新 的多項式次方下界必可增加我們對於電路複雜度的了解。 考慮一個n 個變數布林函數f:{0,1}n→{0,1}與對應的多項式P(x)，目前大多以下 列三種模型來定義多項式表示法：(1)精確表示法P(x)=f(x)∀x.(2)單邊表示法P(x)=0 ⇔f(x)=0.(3)廣義表示法∀x,y s.t. f(x)≠f(y)⇒ P(x)≠P(y).目前對於後兩種模型 的下界所知不多，且都是針對特定函數的結果；例如，And(x)和Modm(x)，但是對於OR(x) 在單邊和廣義兩種表示法的下界卻仍是公開的難題。 近年有學者轉進考慮同時取兩種不同餘數時的多項式次方下界，亦即同時考慮Zp[x] 和Zq[x]中的多項式。考慮一個n 個變數布林函數f，令dp 和dq 分別代表在Zp[x] 和 Zq[x]中可以表示f 的最低次方，目前已知的最好結果是在精確表示法的模型中，任意 的布林函數f 都須符合(log p)×dp×dq×p2dp≥n 的不等式。但是就具體的函數而言，這並 非最佳的結果；此外也依然缺乏在單邊和廣義兩種模型下的結果。本計劃目標是改進此 下界，並從精確表示法模型繼續推廣到單邊和廣義兩種模型。 第一年目標：就「對稱型」布林函數，改進已知次方下界，並推廣到其他模型。 第二年目標：就「非對稱型」布林函數，改進已知次方下界，並推廣到其他模型。

Proving circuit lower bound is a notoriously difficult task in theoretical computer science. Many computational open problems hinge on resolving this barrier. The polynomial method is one of the few known approaches to proving strong circuit lower bounds, where the polynomial degree lower bounds are used to derive circuit lower bounds. This motivates researchers to study the degree lower bound of polynomial representations of Boolean functions. For a given Boolean function f:{0,1}n→{0,1} and a corresponding polynomial P(x), there are three popular representation models in the literature. (1) Exact representation: P(x)=f(x) for all x in {0,1}n.(2) One-sided representation: P(x)=0 ⇔f(x)=0. (3) Generalized representation: for all x,y in {0,1}n s.t. f(x)≠f(y)⇒ P(x)≠P(y). For the one-sided and generalized models, the understanding is much less than the exact representation, and in fact, we only know some specific functions such as And(x) and Modm(x). But for the function OR(x), no one can make sure that whether or not the known lower bound of polynomial degree is tight; it is still an open problem. Recently, some scholars turn to consider the exactly representing polynomials over different fields Zp and Zq, where p and q are different primes. For a given Boolean function, since the exact representing polynomial P(x) in Zp[x] is unique, we can denote the degree as dp. The best known result for any n-variable Boolean function until now is (log p)×dp×dq×p2dp≥n. This inequality is not tight for some specific functions. Furthermore, it is not known to be true or not under one-sided representation and generalized representation. The goal of this project is to investigate the possibility of improvement and extending to general settings. In the first year: we will focus on the symmetric Boolean functions to improve the degree lower bounds. In the second year: we will study the possibility of extending the results to non-symmetric Booleans functions and using the polynomials over rings instead of finite fields.