ISSN:
1420-8954
Keywords:
Complexity of finite functions
;
circuit complexity
;
computation by polynomials
;
relativized complexity
;
68Q15
;
68Q40
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract Define the MOD m -degree of a boolean functionF to be the smallest degree of any polynomialP, over the ring of integers modulom, such that for all 0–1 assignments $$\vec x$$ , $$F(\vec x) = 0$$ iff $$P(\vec x) = 0$$ . We obtain the unexpected result that the MOD m -degree of the OR ofN variables is $$O(\sqrt[\tau ]{N})$$ , wherer is the number of distinct prime factors ofm. This is optimal in the case of representation by symmetric polynomials. The MOD n function is 0 if the number of input ones is a multiple ofn and is one otherwise. We show that the MOD m -degree of both the MOD n and $$\neg MOD_n$$ functions isN Ω(1) exactly when there is a prime dividingn but notm. The MOD m -degree of the MOD m function is 1; we show that the MOD m -degree of $$\neg MOD_m$$ isN Ω(1) ifm is not a power of a prime,O(1) otherwise. A corollary is that there exists an oracle relative to which the MOD m P classes (such as ⊕P) have this structure: MOD m P is closed under complementation and union iffm is a prime power, and MOD n P is a subset of MOD m P iff all primes dividingn also dividem.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01263424
