0
$\begingroup$

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?

Improve this question
$\endgroup$
13
  • $\begingroup$ 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). $\endgroup$
    – Bruno
    Commented Jul 13, 2023 at 7:25
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bruno
    Commented Jul 13, 2023 at 7:29
  • 2
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Jul 13, 2023 at 7:45
  • 2
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Jul 13, 2023 at 7:48
  • $\begingroup$ @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. $\endgroup$
    – tadokoro sinitiro
    Commented Jul 17, 2023 at 18:42

1 Answer 1

Reset to default
1
$\begingroup$

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).

The following posts discuss this:

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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 $\endgroup$
    – tadokoro sinitiro
    Commented Jul 17, 2023 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.