  Given an order, a fundamental problem is deciding whether a univariate
polynomial has a zero. It is a special case of deciding whether
$\text{Hom}(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].
