Faster \(p\)-adic feasibility for certain multivariate sparse polynomials (Q412210): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(7 intermediate revisions by 5 users not shown) | |||
Property / author | |||
Property / author: H. S. Yoon / rank | |||
Normal rank | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65H04 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65Y20 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 12D10 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 12Y05 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6030307 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
feasibility | |||
Property / zbMATH Keywords: feasibility / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
\(p\)-adic rational | |||
Property / zbMATH Keywords: \(p\)-adic rational / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
fewnomial | |||
Property / zbMATH Keywords: fewnomial / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
complexity | |||
Property / zbMATH Keywords: complexity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
short certificate | |||
Property / zbMATH Keywords: short certificate / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
NP-completeness | |||
Property / zbMATH Keywords: NP-completeness / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
sparse | |||
Property / zbMATH Keywords: sparse / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
trinomial | |||
Property / zbMATH Keywords: trinomial / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
multivariate | |||
Property / zbMATH Keywords: multivariate / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Hilbert's Tenth Problem | |||
Property / zbMATH Keywords: Hilbert's Tenth Problem / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Newton polytope | |||
Property / zbMATH Keywords: Newton polytope / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Laurent polynomials | |||
Property / zbMATH Keywords: Laurent polynomials / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Hensel's Lemma | |||
Property / zbMATH Keywords: Hensel's Lemma / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Wagstaff Conjecture | |||
Property / zbMATH Keywords: Wagstaff Conjecture / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
\(p\)-adic rational root | |||
Property / zbMATH Keywords: \(p\)-adic rational root / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Alyson A. Reeves / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2963445336 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1010.5310 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: PRIMES is in P / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: There are infinitely many Carmichael numbers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5522902 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Multivariate ultrametric root counting / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Diophantine Problems Over Local Fields I / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4888749 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Randomization, Sums of Squares, and Faster Real Root Counting for Tetranomials and Beyond / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algorithms in real algebraic geometry / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Faster real feasibility via circuit discriminants / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A CRITERION FOR THE <i>p</i>-ADIC SOLUBILITY OF DIOPHANTINE EQUATIONS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2739443 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3548596 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Straight-line programs and torsion points on elliptic curves / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computing zeta functions of nondegenerate curves / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4011252 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3139838 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Decision procedures for real and <i>p</i>‐adic fields / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4379416 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity estimates depending on condition and round-off error / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hilbert’s Tenth Problem: Relations with Arithmetic and Algebraic Geometry / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4039844 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Counting curves and their projections / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4293510 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Implicit functions from topological vector spaces to Banach spaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Strictly local solutions of diophantine equations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Zeros of <i>p</i> -adic forms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4660637 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Counting solutions to equations in many variables over finite fields / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3615934 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4252163 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Factoring polynomials with rational coefficients / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Cubic homogeneous polynomials over \(\mathfrak p\)-adic number fields / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Efficient \(p\)-adic cell decompositions for univariate polynomials / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bounds for the roots of lacunary polynomials / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4424888 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4947407 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4298260 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New NP-hard and NP-complete polynomial and integer divisibility problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An explicit algebraic family of genus-one curves violating the Hasse principle / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Heuristics for the Brauer–Manin Obstruction for Curves / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Characterization of entire functions via quadrature / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4492826 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4737511 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast Probabilistic Algorithms for Verification of Polynomial Identities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5670687 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4391214 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5343475 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Greatest of the Least Primes in Arithmetic Progressions Having a Given Modulus / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Numbers of solutions of equations in finite fields / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4296321 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 04:00, 5 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Faster \(p\)-adic feasibility for certain multivariate sparse polynomials |
scientific article |
Statements
Faster \(p\)-adic feasibility for certain multivariate sparse polynomials (English)
0 references
4 May 2012
0 references
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.
0 references
feasibility
0 references
\(p\)-adic rational
0 references
fewnomial
0 references
complexity
0 references
short certificate
0 references
NP-completeness
0 references
sparse
0 references
trinomial
0 references
multivariate
0 references
Hilbert's Tenth Problem
0 references
Newton polytope
0 references
Laurent polynomials
0 references
Hensel's Lemma
0 references
Wagstaff Conjecture
0 references
\(p\)-adic rational root
0 references
0 references