A Complexity Chasm for Solving Univariate Sparse Polynomial Equations Over p-adic Fields
A Complexity Chasm for Solving Univariate Sparse Polynomial Equations Over p-adic Fields
We reveal a complexity chasm, separating the trinomial and tetranomial cases, for solving univariate sparse polynomial equations over certain local fields. First, for any fixed field K∈ Q2,,Q3,Q5, …, we prove that any polynomial f Z [x] with exactly 3 monomial terms, degree d, and all coefficients having absolute value …