Polynomial-time root-counting conjecture for fixed-arity sparse polynomials over p-adic fields
Statement
Let and be fixed, and let be an input -nomial, meaning a univariate integer polynomial with at most monomial terms. Root-counting conjecture. There is a polynomial-time algorithm that counts the roots of in . This conjecture proposes a tractable algorithm for root counting over -adic fields when both the prime and the number of monomial terms are fixed. The paper establishes polynomial-time algorithms for related problems for trinomials and shows a complexity barrier for tetranomials with fixed ; counting points on trinomial curves over in time is noted as a challenging open question.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.