论文标题
计算电路支持的系统的多项式时间的真正根源
Counting Real Roots in Polynomial-Time for Systems Supported on Circuits
论文作者
论文摘要
假设$ a = \ {a_1，\ ldots，a_ {n+2} \ subset \ subset \ mathbb {z}^n $具有基数$ n+2 $，并且$ a_j $的所有坐标最多具有绝对价值，最多都不是$ a_j $，并且都不适用于$ a_j $ a_j $ lip All li li lip li li li li li li lip liles act and Ally Alterplane。假设$ f =（f_1，\ ldots，f_n）$是一个$ n \ times n $ polyenmial系统，具有通用整数系数，最多为$ h $，绝对值为$ h $，$ a $ a $ a $ the $ f_i $的指标向量的结合。我们给出第一种算法，对于任何固定的$ n $，都准确计算了$ f $ in Time in Time time pytyramial in $ \ log（dh）$的实际根数。
Suppose $A=\{a_1,\ldots,a_{n+2}\}\subset\mathbb{Z}^n$ has cardinality $n+2$, with all the coordinates of the $a_j$ having absolute value at most $d$, and the $a_j$ do not all lie in the same affine hyperplane. Suppose $F=(f_1,\ldots,f_n)$ is an $n\times n$ polynomial system with generic integer coefficients at most $H$ in absolute value, and $A$ the union of the sets of exponent vectors of the $f_i$. We give the first algorithm that, for any fixed $n$, counts exactly the number of real roots of $F$ in in time polynomial in $\log(dH)$.
