New NP-hard and NP-complete polynomial and integer divisibility problems

DOI10.1016/0304-3975(84)90130-0zbMath0572.68027OpenAlexW2031046967MaRDI QIDQ1062447

David Alan Plaisted

Publication date: 1984

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(84)90130-0

zbMATH Keywords

differential equationsNP-completenessrecurrence relationsNP-hardnesssparse polynomialseigenvalues of sparse matricesinteger divisibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Polynomials in real and complex fields: factorization (12D05)

Related Items

Irreducibility of multivariate polynomials, Complete divisibility problems for slowly utilized oracles, Computing the torsion points of a variety defined by lacunary polynomials, Feasible arithmetic computations: Valiant's hypothesis, Digital collections of examples in mathematical sciences, Faster \(p\)-adic feasibility for certain multivariate sparse polynomials, Detecting lacunary perfect powers and computing their roots, On the frontiers of polynomial computations in tropical geometry, Real roots of univariate polynomials and straight line programs, Counting curves and their projections, Metric estimates and membership complexity for Archimedean amoebae and tropical hypersurfaces, Efficient algorithms for sparse cyclotomic integer zero testing, Complexity aspects of a semi-infinite optimization problem†, Correction to: ``Tropical varieties for exponential sums, Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields, Tropical varieties for exponential sums, Some speed-ups and speed limits for real algebraic geometry

Cites Work

• Sparse complex polynomials and polynomial reducibility
• Every Prime Has a Succinct Certificate
• Some Polynomial and Integer Divisibility Problems are $NP$-Hard
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item