The Radical Solution and Computational Complexity

2024/05/04 by Bojin Zheng, Zheng, Bojin, Weiwu Wang +1
Computer Science · #Computational Complexity (cs.CC) #Computational Drug Discovery Methods #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2405.15790

openalex publication_date 2024/05/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The radical solution of polynomials with rational coefficients is a famous solved problem. This paper found that it is a \mathbbNP problem. Furthermore, this paper found that arbitrary \mathscrP ∈ ℙ shall have a one-way running graph G, and have a corresponding \mathscrQ ∈ \mathbbNP which have a two-way running graph G', G and G' is isomorphic, i.e., G' is combined by G and its reverse G^-1. When \mathscrP is an algorithm for solving polynomials, G^-1 is the radical formula. According to Galois' Theory, a general radical formula does not exist. Therefore, there exists an \mathbbNP, which does not have a general, deterministic and polynomial time-complexity algorithm, i.e., ℙ ≠ \mathbbNP. Moreover, this paper pointed out that this theorem actually is an impossible trinity.

Related

• An Algorithm for Solving Solvable Polynomial Equations of Arbitrary Degree by Radicals
• Computational complexity of solving polynomial differential equations over unbounded domains with non-rational coefficients
• Solvability of cubic and quartic equations using one radical
• Galois Theory without abstract algebra
• Some more proofs from the Book: solvability and insolvability of equations in radicals