Rojas J Maurice
Department of Mathematics, Texas A & M University, TAMU 3368, College Station, TX 77843-3368 USA.
Found Comut Math. 2022 Nov 28:1-43. doi: 10.1007/s10208-022-09599-z.
Suppose has cardinality , with all the coordinates of the having absolute value at most , and the do all lie in the same affine hyperplane. Suppose is an polynomial system with generic integer coefficients at most in absolute value, and the union of the sets of exponent vectors of the . We give the first algorithm that, for any , counts exactly the number of real roots of in time polynomial in . We also discuss a number-theoretic hypothesis that would imply a further speed-up to time polynomial in as well.
假设(\mathbf{a})的基数为(n)，(\mathbf{a})的所有坐标的绝对值至多为(M)，并且(\mathbf{a})并不都位于同一个仿射超平面内。假设(f)是一个(n)元多项式系统，其系数为绝对值至多为(D)的一般整数，(E)是(f)的指数向量集的并集。我们给出了第一种算法，对于任意(\epsilon\gt0)，该算法能在(n)的多项式时间内精确计算(f)的实根数量。我们还讨论了一个数论假设，该假设将意味着进一步加速至(n)的多项式时间。
