Faster p-adic feasibility for certain multivariate sparse polynomials

DOI10.1016/J.JSC.2011.09.007MaRDI QIDQ412210zbMATH OpenOpenAlexFDO

Authors Martín Avendaño, Ashraf Ibrahim, J. Maurice Rojas, Korben Rusek

Publication date 4 May 2012

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.5310

zbMATH Keywords

multivariatecomplexityNP-completenesssparsefeasibilityLaurent polynomialsNewton polytopefewnomialtrinomialHilbert's Tenth Problem\(p\)-adic rational\(p\)-adic rational rootHensel's Lemmashort certificateWagstaff Conjecture

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Numerical computation of roots of polynomial equations (65H04) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10)

Abstract: We present algorithms revealing new families of polynomials allowing sub-exponential detection of p-adic rational roots, relative to the sparse encoding. For instance, we show that the case of honest n-variate (n+1)-nomials is doable in NP and, for p exceeding the Newton polytope volume and not dividing any coefficient, in constant time. Furthermore, using the theory of linear forms in p-adic logarithms, we prove that the case of trinomials in one variable can be done in NP. The best previous complexity bounds for these problems were EXPTIME or worse. Finally, we prove that detecting p-adic rational roots for sparse polynomials in one variable is NP-hard with respect to randomized reductions. The last proof makes use of an efficient construction of primes in certain arithmetic progressions. The smallest n where detecting p-adic rational roots for n-variate sparse polynomials is NP-hard appears to have been unknown.

Recommendations

• Randomized NP-completeness for p -adic rational roots of sparse polynomials in one variable
• Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields
• Faster real feasibility via circuit discriminants
• Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields
• Sublinear root detection and new hardness results for sparse polynomials over finite fields

Cites work

• scientific article; zbMATH DE number 1643926 (Why is no real title available?)
• scientific article; zbMATH DE number 435565 (Why is no real title available?)
• scientific article; zbMATH DE number 5532114 (Why is no real title available?)
• scientific article; zbMATH DE number 66619 (Why is no real title available?)
• scientific article; zbMATH DE number 192960 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305294 (Why is no real title available?)
• scientific article; zbMATH DE number 575960 (Why is no real title available?)
• scientific article; zbMATH DE number 591019 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1121901 (Why is no real title available?)
• scientific article; zbMATH DE number 1157649 (Why is no real title available?)
• scientific article; zbMATH DE number 1978269 (Why is no real title available?)
• scientific article; zbMATH DE number 1482142 (Why is no real title available?)
• scientific article; zbMATH DE number 2151173 (Why is no real title available?)
• scientific article; zbMATH DE number 2086908 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• scientific article; zbMATH DE number 3216342 (Why is no real title available?)
• scientific article; zbMATH DE number 3235209 (Why is no real title available?)
• scientific article; zbMATH DE number 3404329 (Why is no real title available?)
• A CRITERION FOR THE p-ADIC SOLUBILITY OF DIOPHANTINE EQUATIONS
• Algorithms in real algebraic geometry
• An explicit algebraic family of genus-one curves violating the Hasse principle
• Bounds for the roots of lacunary polynomials
• Characterization of entire functions via quadrature
• Complexity estimates depending on condition and round-off error
• Computing zeta functions of nondegenerate curves
• Counting (quickly) the number of solutions of equations in finite fields
• Counting curves and their projections
• Counting solutions to equations in many variables over finite fields
• Cubic homogeneous polynomials over \(\mathfrak p\)-adic number fields
• Decision procedures for real and p‐adic fields
• Diophantine Problems Over Local Fields I
• Efficient \(p\)-adic cell decompositions for univariate polynomials
• Factoring polynomials with rational coefficients
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Faster real feasibility via circuit discriminants
• Greatest of the Least Primes in Arithmetic Progressions Having a Given Modulus
• Heuristics for the Brauer–Manin Obstruction for Curves
• Hilbert’s Tenth Problem: Relations with Arithmetic and Algebraic Geometry
• Implicit functions from topological vector spaces to Banach spaces
• Multivariate ultrametric root counting
• New NP-hard and NP-complete polynomial and integer divisibility problems
• Numbers of solutions of equations in finite fields
• PRIMES is in P
• Randomization, sums of squares, near-circuits, and faster real root counting
• Straight-line programs and torsion points on elliptic curves
• Strictly local solutions of diophantine equations
• There are infinitely many Carmichael numbers
• Zeros of \(p\)-adic forms

Cited in

(13)

• Computing zeta functions of large polynomial systems over finite fields
• Solvability of cubic equations in \(p\)-adic integers \((p>3)\)
• Randomized polynomial-time root counting in prime power rings
• Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields
• Counting roots for polynomials modulo prime powers
• \#P-completeness of counting roots of a sparse polynomial
• Randomized NP-completeness for p -adic rational roots of sparse polynomials in one variable
• Recurrent properties of quasi-periodic dynamical systems with multiple frequencies of \(p\)-adic Liouville numbers
• Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields
• On cubic equations over \(p\)-adic fields
• A complexity chasm for solving sparse polynomial equations over \(p\)-adic fields. Extended abstract
• A complexity chasm for solving univariate sparse polynomial equations over \(p\)-adic fields
• Sublinear root detection and new hardness results for sparse polynomials over finite fields

This page was built for publication: Faster \(p\)-adic feasibility for certain multivariate sparse polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412210)