New NP-hard and NP-complete polynomial and integer divisibility problems
From MaRDI portal
Publication:1062447
DOI10.1016/0304-3975(84)90130-0zbMath0572.68027OpenAlexW2031046967MaRDI QIDQ1062447
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
differential equationsNP-completenessrecurrence relationsNP-hardnesssparse polynomialseigenvalues of sparse matricesinteger divisibility
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
