论文标题
三项元素和确定性复杂性限制
Trinomials and Deterministic Complexity Limits for Real Solving
论文作者
论文摘要
我们详细介绍了一种算法 - 除了$ \ frac {1} {ω（\ log（dh））} $分数$ f \ in \ mathbb {z} [x] $，恰好$ 3 $ nomial cormial corgeients in \ mathbb {z} [x] $，以及$ \ \ \ f的所有系数，以及所有这些系数。 smale）对于确定性时间$ \ log^{4+o（1）}（dh）$中的每个真实根，在经典图灵模型中。 （每个近似根都是一个合理的，具有对数高度$ o（\ log（dh））$。）最好的先前确定性位复杂性界限是$ \ log d $中的指数。然后，我们将其与Koiran的三项典范问题（2017）联系起来：确定$ d $ d $ d $ d $ trinomial $ f \ in \ mathbb {z} [x] [x] $与$ \ { - h，\ ldots，h \ \} $中的系数，$ r \！ h $，in（确定性）时间$ \ log^{o（1）}（dh）$。我们表明，Koiran的Trinomial标志问题承认了一个积极的解决方案，至少对于输入$（f，r）$的分数$ 1- \ frac {1} {ω（\ log（dh））} $。
We detail an algorithm that -- for all but a $\frac{1}{Ω(\log(dH))}$ fraction of $f\in\mathbb{Z}[x]$ with exactly $3$ monomial terms, degree $d$, and all coefficients in $\{-H,\ldots, H\}$ -- produces an approximate root (in the sense of Smale) for each real root of $f$ in deterministic time $\log^{4+o(1)}(dH)$ in the classical Turing model. (Each approximate root is a rational with logarithmic height $O(\log(dH))$.) The best previous deterministic bit complexity bounds were exponential in $\log d$. We then relate this to Koiran's Trinomial Sign Problem (2017): Decide the sign of a degree $d$ trinomial $f\in\mathbb{Z}[x]$ with coefficients in $\{-H,\ldots,H\}$, at a point $r\!\in\!\mathbb{Q}$ of logarithmic height $\log H$, in (deterministic) time $\log^{O(1)}(dH)$. We show that Koiran's Trinomial Sign Problem admits a positive solution, at least for a fraction $1-\frac{1}{Ω(\log(dH))}$ of the inputs $(f,r)$.
