The complexity of root-finding in orders

MaRDI QIDQ6358361zbMATH OpenFDO

Authors Pim Spelier

Publication date 15 January 2021

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Other algebras and orders, and their zeta and (L)-functions (11R54) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: Given an order, a fundamental problem is deciding whether a univariate polynomial has a zero. It is a special case of deciding whether $extHom(A,B)$ is non-empty for two orders $A$ and $B$. For fixed separable orders, deciding whether a polynomial has a zero is in $P$. If we instead fix a separable polynomial, the problem is NP-complete with probability $1$. We provide several theorems about NP-completeness, culminating into a complete classification of the problem for quadratic and cubic polynomials. A main ingredient is a new type of algebraic NP-complete group-theoretic problems, as seen in [Spe21].

This page was built for publication: The complexity of root-finding in orders

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