Complexity of solving a higher-order degree polynomial equation? P-problem or NP-problem or neither?

I am a mathematician and I am very new to theoretical computer science.

The definition of P/NP problem I found in wiki is that:

• P is the set of decision problems solvable in polynomial time by a deterministic Turing machine.
• NP is the set of decision problems solvable in polynomial time by a nondeterministic Turing machine.
• NP is the set of decision problems verifiable in polynomial time by a deterministic Turing machine.

Consider the problem of solving a one-variable higher-order degree polynomial equation(e.g., find all $$x$$ satisfied with $$x^5+c_4x^4+c_3x^3+c_2x^2+c_1x^1+c_0=0$$ with given $$c_i \in \mathbb{C}$$). Mathematicians have proved that for degree $$\geq 5$$ the polynomial equation does not have algebraic (changed the word 'analytic' to 'algebraic', thank Emil Jeřábek) solutions (See Abel–Ruffini theorem).

Hence, by the definition of P/NP complexity, this problem should not be in P class (otherwise we can get the solution for degree $$\geq 5$$ equations in polynomial time). And this problem can be verified in polynomial time, does that mean this problem in NP class? Or not? And Why?

Also, I found a paper called "On phase retrieval of finite-length sequences using the initial time sample", Haralambos Sahinoglou and Sergio Cabrera, IEEE Transactions on Circuits and Systems, 1991. In Section 2 and Section 3 of this paper, the authors state that they can get all the zeros of any one-variable high-order polynomial $$R(z)$$ and then form the zeros to a NP-complete problem, as a result, they can prove their original problem is NP-complete. Why do they believe that finding any polynomial's zeros can be done?

• The fact that degree-$≥5$ polynomial equations have no implication whatsoever about the problem belonging or not to $\mathsf P$. One can complement Neal's answer: There are polynomial-time algorithms for polynomial root finding over many rings: $ℤ$, $ℚ$, number fields, $𝔽_q$, even some algebraic closures, etc. It is also the case over $ℝ$ or $ℂ$ once you properly define your problem (with approximate values). Jul 13, 2023 at 7:25
• The reason for no implication is that Abel-Ruffini theorem states that there is no solutions in radicals but general algorithms have no reason to use only radicals for computing the roots. Jul 13, 2023 at 7:29
• You are confusing two different meanings of the word: "solvability" of a polynomial equation by an expression in radicals has nothing to do with "solvability" of a decision problem by an efficient algorithm. Jul 13, 2023 at 7:45
• Also, the Abel–Ruffini theorem says nothing about analytic solutions. All polynomials have analytic solutions. The theorem is about algebraic solutions by means of radicals. Jul 13, 2023 at 7:48
• @Bruno Thanks for your comments. I understand that you mentioned the general algorithms for computing roots must not base on radicals, as a result, if there is a set of all (base) P-complexity mathematical operations (like radicals, add/minus, multiplication/division) defined in the theoretical computer science field? Also, if there is a formal definition of deterministic Turing machine process/algorithm and where can I find it? The descriptions on online websites (like Wiki) are hard to understand. Jul 17, 2023 at 18:42