Randomized NP-completeness for p -adic rational roots of sparse polynomials in one variable

DOI10.1145/1837934.1837997MaRDI QIDQ2946560zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 17 September 2015

Published in Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1837934.1837997

zbMATH Keywords

\(p\)-adicarithmetic progressionfeasibilityNPsparse

Mathematics Subject Classification ID

Other nonanalytic theory (11S85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Symbolic computation and algebraic computation (68W30)

Recommendations

• A complexity chasm for solving sparse polynomial equations over \(p\)-adic fields. Extended abstract
• Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields
• Faster p-adic feasibility for certain multivariate sparse polynomials
• \#P-completeness of counting roots of a sparse polynomial
• Sublinear root detection and new hardness results for sparse polynomials over finite fields
• Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields
• Sparse univariate polynomials with many roots over finite fields
• Roots of sparse polynomials over a finite field
• Computing the roots of sparse high-degree polynomials that arise from the study of random simplicial complexes
• Complexity bounds for the rational Newton-Puiseux algorithm over finite fields

Cites work

• Differential algebra for derivations with nontrivial commutation rules
• Differential invariants of a Lie group action: syzygies on a generating set
• Differential invariants of conformal and projective surfaces
• Generating differential invariants
• Higher order contact of submanifolds of homogeneous spaces
• scientific article; zbMATH DE number 3762913 (Why is no real title available?)
• scientific article; zbMATH DE number 45257 (Why is no real title available?)
• scientific article; zbMATH DE number 3490133 (Why is no real title available?)
• scientific article; zbMATH DE number 2038305 (Why is no real title available?)
• scientific article; zbMATH DE number 2142844 (Why is no real title available?)
• scientific article; zbMATH DE number 3015982 (Why is no real title available?)
• scientific article; zbMATH DE number 802623 (Why is no real title available?)
• Invariants différentiels d'un pseudogroupe de Lie. I
• Invariants différentiels d'un pseudogroupe de Lie. II
• Moving coframes. II: Regularization and theoretical foundations
• Projective-type differential invariants and geometric curve evolutions of KdV-type in flat homogeneous manifolds
• Rational invariants of a group action. Construction and rewriting
• Smooth and algebraic invariants of a group action: Local and global constructions

Cited in

(7)

• \#P-completeness of counting roots of a sparse polynomial
• Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields
• Real roots of univariate polynomials and straight line programs
• Solvability of cubic equations in \(p\)-adic integers \((p>3)\)
• Faster p-adic feasibility for certain multivariate sparse polynomials
• A complexity chasm for solving sparse polynomial equations over \(p\)-adic fields. Extended abstract
• Randomized polynomial-time root counting in prime power rings

Describes a project that uses

Uses Software

• DIFFALG
• AIDA

This page was built for publication: Randomized NP-completeness for p -adic rational roots of sparse polynomials in one variable

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