期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：study the following problem raised by von zur Gathen and Roche:
What is the minimal degree of a nonconstant polynomial f:0n0m ?
Clearly, when m=n the function f(x)=x has degree 1. We prove that when m=n−1 (i.e. the point n is not in the range), it must be the case that deg(f)=n−o(n). This shows an interesting threshold phenomenon. In fact, the same bound on the degree holds even when the image of the polynomial is any (strict) subset of 0n . Going back to the case m=n, as we noted the function f(x)=x is possible, however, we show that if one excludes all degree 1 polynomials then it must be the case that deg(f)=n−o(n). Furthermore, the same conclusion holds even if m=O(n1475−). In other words, there are no polynomials of intermediate degrees that map 0n to 0m .
Moreover, we give a meaningful answer when m is a large polynomial, or even exponential, in n. Consider the case m=1d!2en−dd . f can of
course be a degree d−1 polynomial, e.g., f(x)=xd−1 or even f(x)=d−1x−n2 (whose range is bounded by n2d−1 ). We show that when d2n15 , either deg(f)d−1 or f must satisfy deg(f)n3−O(dlogn) . Stated differently, if we remove the `trivial' cases where f is of degree at most d−1, the next example must have a very high degree. So, again, no polynomial of intermediate degree mapping 0n to 01d!2en−dd exists.
We complement these results by showing that for every d=o(nlogn) there exists a polynomial f:0n0O(nd+05) of degree n3−O(dlogn)deg(f)n−O(dlog(n)) .
Our work considerably extends the results of von zur Gathen and Roche that studied the case m=1.
