How to find a non-zero point of a non-zero polynomial of low degree?

If (ceil(degree/n))+1 is "large", then there doesn't actually need to be such an X$\hspace{.02 in}$'.
$\Bigg(\hspace{-0.08 in}$The polynomial can be $\;\;\; \displaystyle\prod_{i\hspace{.02 in}\in \hspace{.02 in}\text{coordinates}} \: \left(\displaystyle\prod_{c\hspace{.02 in}\in (\mathbb{F}\hspace{.03 in}-\{0\})} (x_{\hspace{.02 in}i}-c)\hspace{-0.07 in}\right) \;\;\;$ and X can be the origin.$\hspace{-0.08 in}\Bigg)$

If "large" means larger than 1 plus [the minimum over the variables of the degree in that variable], then there's a uniform NC$^0$ algorithm that will, with no access to the polynomial, with neither
bit operations nor field operations nor equality tests on field elements ($\hspace{.03 in}$just copying them and
moving them around), output a polynomial-length list of elements of $\mathbb{F}^n$ such that at least one
of those elements is such an X'. (When B is an upper bound on the bracketed expression from
the previous sentence, the algorithm will have B+2 distinct hard-coded field elements and output the n$\cdot$(B+2) results of replacing one of X's coordinates with one of the B+2 field elements.)

Thus, you need to either consider fields of "intermediate" size, or allow polynomials of
large (superpolynomial) degree. (Arithmetic circuits can easily have exponential degree.)

A problem that's closer to canonical for FRP PPP (and is actually obviously in PPP) is


Input: A (circuit encoding a) function f : {0,1}ⁿ⁺¹ -> {0,1}ⁿ
and a (circuit encoding a) function g : {0,1}ⁿ -> {0,1}ⁿ⁺¹

Correct Outputs: elements x of {0,1}ⁿ⁺¹ such that g(f(x)) x


.

Solved by user6973 (0 )
Jan 12, 2016 at 08:32