<p>Finding the factorization of a single-variable polynomial with rational coefficients is apparently solvable in poly time, as shown in [1]:</p>
<p>[1] Lenstra, A. K.; Lenstra, H. W., Jr.; Lovász, L. Factoring polynomials with rational coefficients. Math. Ann. 261 (1982), no. 4, 515–534. (<a href="https://scholar.google.com/scholar?cluster=4657557835140974516&amp;hl=en&amp;as_sdt=0,22&amp;as_vis=1" rel="nofollow noreferrer">link</a>).</p>
<p>The following posts discuss this:</p>
<ul>
<li><p><a href="https://mathoverflow.net/questions/97329/complexity-of-finding-a-rational-root-of-a-polynomial">https://mathoverflow.net/questions/97329/complexity-of-finding-a-rational-root-of-a-polynomial</a></p>
</li>
<li><p><a href="https://mathoverflow.net/questions/97307/polynomials-all-of-whose-roots-are-rational">https://mathoverflow.net/questions/97307/polynomials-all-of-whose-roots-are-rational</a></p>
</li>
</ul>
<p>This presumably gives you a polynomial-time algorithm to find all the <em>real</em> roots.   Are you also interested in finding non-real (complex) roots?</p>

CC BY-SA 4.0
2023-07-17T18:04:08.563Z
I feel sorry that my question is not clear. My original question is that, what is the complexity of finding all "complex" roots of a single-variable polynomial with "complex" coefficients. Also, I want to ask the complexity of finding all "complex" roots of a single-variable polynomial with "real" coefficients. Thanks for your answer to the complexity of "real" roots with "rational" coefficients
tadokoro sinitiro
CC BY-SA 4.0
2023-07-12T23:43:11.877Z
2023-07-12T23:43:11.877Z
Neal Young
<p>I am a mathematician and I am very new to theoretical computer science.</p>
<p>The definition of P/NP problem I found in wiki is that:</p>
<ul>
<li>P is the set of decision problems <strong>solvable</strong> in polynomial time by a <strong>deterministic</strong> Turing machine.</li>
<li>NP is the set of decision problems <strong>solvable</strong> in polynomial time by a <strong>nondeterministic</strong> Turing machine.</li>
<li>NP is the set of decision problems <strong>verifiable</strong> in polynomial time by a <strong>deterministic</strong> Turing machine.</li>
</ul>
<p>Consider the problem of solving a one-variable higher-order degree polynomial equation(e.g., find all <span class="math-container">$x$</span> satisfied with <span class="math-container">$x^5+c_4x^4+c_3x^3+c_2x^2+c_1x^1+c_0=0$</span> with given <span class="math-container">$c_i \in \mathbb{C}$</span>). Mathematicians have proved that for degree <span class="math-container">$\geq 5$</span> the polynomial equation does not have <strong>algebraic</strong> (changed the word 'analytic' to 'algebraic', thank Emil Jeřábek) solutions (See Abel–Ruffini theorem).</p>
<p>Hence, by the definition of P/NP complexity, this problem should not be in P class (otherwise we can get the solution for degree <span class="math-container">$\geq 5$</span> 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?</p>
<p>Also, I found a paper called <a href="https://www.academia.edu/63116964/On_phase_retrieval_of_finite_length_sequences_using_the_initial_time_sample" rel="nofollow noreferrer">&quot;On phase retrieval of finite-length sequences using the initial time sample&quot;</a>, 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 <strong>any</strong> one-variable high-order polynomial <span class="math-container">$R(z)$</span> 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?</p>

CC BY-SA 4.0
2023-07-13T07:25:27.617Z
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).
Bruno
CC BY-SA 4.0
2023-07-13T07:29:20.503Z
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.
Bruno
CC BY-SA 4.0
2023-07-13T07:45:31.237Z
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.
Emil Jeřábek
CC BY-SA 4.0
2023-07-13T07:48:25.057Z
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*.
Emil Jeřábek
CC BY-SA 4.0
2023-07-17T18:42:43.883Z
@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.
tadokoro sinitiro
CC BY-SA 4.0
2023-07-17T19:04:59.463Z
@EmilJeřábek Yes, you are correct, before I read your answer, I am confused about the meaning of "solvability". Is there a formal definition of "solvability" of a decision problem by an efficient algorithm? I am new to this field and I feel sorry that it is hard for me to understand the connection between the deterministic turning machine process and a specific deterministic algorithm (like radical)
tadokoro sinitiro
CC BY-SA 4.0
2023-07-18T12:27:12.720Z
@tadokorosinitiro You're asking questions about extremely basic notions of theoretical computer science, unsuited for this "research-level TCS community." You should try to ask questions on cs.stackexchange.com instead. To make my comment more useful, of course all these notions are perfectly defined, and you should have a look to any introductory book on complexity theory. The online book [Introduction to Theoretical Computer Science](https://introtcs.org/) may be a start. Chapter 13 is what you request, though you may need to look at previous chapters too.
Bruno
CC BY-SA 4.0
2023-07-18T21:57:23.637Z
@Bruno Thanks for you comment. I will read the book in the next few weeks. I have an additional question about the complexity of finding the roots of polynomial. In the paper [On phase retrieval of finite-length sequences using the initial time sample](https://www.academia.edu/63116964/On_phase_retrieval_of_finite_length_sequences_using_the_initial_time_sample), the authors assume that they can find all "complex" roots of high-order polynomial $R(z)$ with "real" coefficient efficiently (if their proof is acceptable, the complexity of such a process should be P, which makes me confused).
tadokoro sinitiro
CC BY-SA 4.0
2023-07-19T09:45:14.947Z
I cannot answer your question: what is "high-order"? what is "efficiently"? In any case, computing the complex roots of a real polynomial can be done in polynomial time. Of course, you have to precisely define what "computing" means here (since the roots may have infinitely many decimals say). The following paper gives the fastest algorithm for isolating the complex roots, in quasi-linear time: [New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems](https://ieeexplore.ieee.org/document/9719717).
Bruno
CC BY-SA 4.0
2023-07-19T17:56:31.057Z
@Bruno Sorry for my unclear question. My question is that, why the authors in the paper I listed in previous comments can assume **finding** all "complex" roots of polynomial () with degree >=5 and "real" coefficient can be done in P-complexity? Here, the **finding** means getting the exact roots analytically, or mathematically (framing the solution in a finite-step well-understood form by basic mathematical functions (like radical, add/multiply, or other basic functions defined in TCS field)).
tadokoro sinitiro
CC BY-SA 4.0
2023-07-19T18:04:41.330Z
I understand computing the complex roots of a real polynomial can be done in polynomial time, but here the **computing** means getting the roots **numerically**, which is completely different from solving an equation 'analytically'.
tadokoro sinitiro
CC BY-SA 4.0
2023-07-20T09:28:50.723Z
@tadokorosinitiro Skimming through the paper, I do not get why you assume that *finding* has the meaning you mention. Actually, *exactly* computing the roots has no sense in the standard (Turing machine) model of computation. To study such kind of questions, you need a complex number (thus non-realistic) model of computation such as the [BSS model](https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine) (or [Real RAM](https://en.wikipedia.org/wiki/Real_RAM)). In this model, the [problem is undecidable](https://cs.stackexchange.com/a/46993/8532).
Bruno
CC BY-SA 4.0
2023-07-20T09:34:58.563Z
Finally, I do not understand what you are looking for. One problem is that your "basic mathematical functions" are undefined (in TCS or elsewhere). If you are trying to understand the paper you cite, it seems to me (I did not read it carefully though) that the authors work with very standard approximate representations of real/complex numbers, and their root computations are numeric. If you are interested in modelling computation on exact real/complex numbers, then you should read the [Blum-Cucker-Shub-Smale book](https://link.springer.com/book/10.1007/978-1-4612-0701-6).
Bruno
<cc.complexity-theory><np-hardness><algebra><p-vs-np>
Complexity of solving a higher-order degree polynomial equation? P-problem or NP-problem or neither?
tadokoro sinitiro
# Complexity of solving a higher-order degree polynomial equation? P-problem or NP-problem or neither?

(Asked by: username_0 on 2023-07-12)

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"](https://www.academia.edu/63116964/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?

**Tags:** cc.complexity-theory, np-hardness, algebra, p-vs-np
> **Comments:**
> **username_1**: 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).  
> **username_1**: 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.  
> **username_2**: 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.  
> **username_2**: 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*.  
> **username_0**: @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.  
> **username_0**: @EmilJeřábek Yes, you are correct, before I read your answer, I am confused about the meaning of "solvability". Is there a formal definition of "solvability" of a decision problem by an efficient algorithm? I am new to this field and I feel sorry that it is hard for me to understand the connection between the deterministic turning machine process and a specific deterministic algorithm (like radical)  
> **username_1**: @tadokorosinitiro You're asking questions about extremely basic notions of theoretical computer science, unsuited for this "research-level TCS community." You should try to ask questions on cs.stackexchange.com instead. To make my comment more useful, of course all these notions are perfectly defined, and you should have a look to any introductory book on complexity theory. The online book [Introduction to Theoretical Computer Science](https://introtcs.org/) may be a start. Chapter 13 is what you request, though you may need to look at previous chapters too.  
> **username_0**: @Bruno Thanks for you comment. I will read the book in the next few weeks. I have an additional question about the complexity of finding the roots of polynomial. In the paper [On phase retrieval of finite-length sequences using the initial time sample](https://www.academia.edu/63116964/On_phase_retrieval_of_finite_length_sequences_using_the_initial_time_sample), the authors assume that they can find all "complex" roots of high-order polynomial $R(z)$ with "real" coefficient efficiently (if their proof is acceptable, the complexity of such a process should be P, which makes me confused).  
> **username_1**: I cannot answer your question: what is "high-order"? what is "efficiently"? In any case, computing the complex roots of a real polynomial can be done in polynomial time. Of course, you have to precisely define what "computing" means here (since the roots may have infinitely many decimals say). The following paper gives the fastest algorithm for isolating the complex roots, in quasi-linear time: [New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems](https://ieeexplore.ieee.org/document/9719717).  
> **username_0**: @Bruno Sorry for my unclear question. My question is that, why the authors in the paper I listed in previous comments can assume **finding** all "complex" roots of polynomial () with degree >=5 and "real" coefficient can be done in P-complexity? Here, the **finding** means getting the exact roots analytically, or mathematically (framing the solution in a finite-step well-understood form by basic mathematical functions (like radical, add/multiply, or other basic functions defined in TCS field)).  
> **username_0**: I understand computing the complex roots of a real polynomial can be done in polynomial time, but here the **computing** means getting the roots **numerically**, which is completely different from solving an equation 'analytically'.  
> **username_1**: @tadokorosinitiro Skimming through the paper, I do not get why you assume that *finding* has the meaning you mention. Actually, *exactly* computing the roots has no sense in the standard (Turing machine) model of computation. To study such kind of questions, you need a complex number (thus non-realistic) model of computation such as the [BSS model](https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine) (or [Real RAM](https://en.wikipedia.org/wiki/Real_RAM)). In this model, the [problem is undecidable](https://cs.stackexchange.com/a/46993/8532).  
> **username_1**: Finally, I do not understand what you are looking for. One problem is that your "basic mathematical functions" are undefined (in TCS or elsewhere). If you are trying to understand the paper you cite, it seems to me (I did not read it carefully though) that the authors work with very standard approximate representations of real/complex numbers, and their root computations are numeric. If you are interested in modelling computation on exact real/complex numbers, then you should read the [Blum-Cucker-Shub-Smale book](https://link.springer.com/book/10.1007/978-1-4612-0701-6).  

---

## 1 answers

### Answer by username_3 on 2023-07-12. Score: 1

Finding the factorization of a single-variable polynomial with rational coefficients is apparently solvable in poly time, as shown in [1]:

[1] Lenstra, A. K.; Lenstra, H. W., Jr.; Lovász, L. Factoring polynomials with rational coefficients. Math. Ann. 261 (1982), no. 4, 515–534. ([link](https://scholar.google.com/scholar?cluster=4657557835140974516&hl=en&as_sdt=0,22&as_vis=1)).

The following posts discuss this:

* <https://mathoverflow.net/questions/97329/complexity-of-finding-a-rational-root-of-a-polynomial>
* <https://mathoverflow.net/questions/97307/polynomials-all-of-whose-roots-are-rational>

This presumably gives you a polynomial-time algorithm to find all the *real* roots. Are you also interested in finding non-real (complex) roots?

> **Comments:**
> **username_0**: I feel sorry that my question is not clear. My original question is that, what is the complexity of finding all "complex" roots of a single-variable polynomial with "complex" coefficients. Also, I want to ask the complexity of finding all "complex" roots of a single-variable polynomial with "real" coefficients. Thanks for your answer to the complexity of "real" roots with "rational" coefficients  

---

