Faster \(p\)-adic feasibility for certain multivariate sparse polynomials (Q412210): Difference between revisions

For an input Laurent polynomial system \(F \in \bigcup_{k,n \in \mathbb{N}}( \mathbb{Z}[x_1^{\pm 1},\dots,x_n^{\pm 1}])^k\), let \(\text{FEAS}_{\mathbb{Q}_{\text{primes}}}\) denote the problem of deciding whether \(F\) has a \(p\)-adic rational root. If \(f(x) := \sum_{j=1}^m c_jx^{a_j}\), with \(c_j \in \mathbb{R}\setminus \{0\}\) for all \(j\), and \(x^{a_j} = x_1^{a_{1j}}\cdots x_n^{a_{nj}}\), then size(\(f\)) := \(\sum_{i=1}^m \log_2[(2+|c_i|)(2+|a_{1j}|) \cdots (2+|a_{nj}|)\). When the prime \(p\) is fixed, the input size will be size(\(f\)), but when the prime \(p\) is allowed to range over all or a subfamily of primes, the input size will be \(\text{size}(f)+\log(p)\). Size\((F)\) is the sum of the sizes of the polynomials defining \(F\). If the \(a_j\) are pairwise distinct, \(f\) is an \textit{\(n\)-variate \(m\)-nomial}. If, additionally, the volume of the Newton polytope of \(f\) is positive, \(f\) is said to be an \textit{honest \(n\)-variate \(m\)-nomial}. Only honest \(n\)-variate \(m\)-nomials are considered in the paper. Given the above definitions, the authors prove that the detection of \(p\)-adic rational roots is: {\parindent=7mm \begin{itemize}\item[{\(*\)}]\textbf{NP}-complete for honest \(n\)-variate (\(n+1\))-nomials, \item[{\(*\)}]of constant-time complexity for certain special families of \(n\)-variate (\(n+1\))-nomials when \(p\) exceeds the Newton polytope volume \item[{\(*\)}]\textbf{NP} for trinomials in one variable \item[{\(*\)}]\textbf{NP}-hard for sparse polynomials in one variable with respect to randomized reductions. \end{itemize}} Additionally, the authors prove that, for \(f \in \mathbb{Z}[x_1]\), if there were randomized algorithms of expected complexity polynomial in \(\text{size}(f)+\log(p)\) for factoring \(f\) over \(\mathbb{Q}_p[x_1]\), then \textbf{NP} \(\subseteq\) \textbf{ZPP}. The univariate \textbf{NP}-hardness proof requires the efficient construction of primes in certain arithmetic progressions, which the authors also prove possible.