Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2405.15790 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911886780399616 |
|---|---|
| author | Zheng, Bojin Wang, Weiwu |
| author_facet | Zheng, Bojin Wang, Weiwu |
| contents | The radical solution of polynomials with rational coefficients is a famous solved problem. This paper found that it is a $\mathbb{NP}$ problem. Furthermore, this paper found that arbitrary $ \mathscr{P} \in \mathbb{P}$ shall have a one-way running graph $G$, and have a corresponding $\mathscr{Q} \in \mathbb{NP}$ 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 $\mathscr{P}$ 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 $\mathbb{NP}$, which does not have a general, deterministic and polynomial time-complexity algorithm, i.e., $\mathbb{P} \neq \mathbb{NP}$. Moreover, this paper pointed out that this theorem actually is an impossible trinity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_15790 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Radical Solution and Computational Complexity Zheng, Bojin Wang, Weiwu Computational Complexity The radical solution of polynomials with rational coefficients is a famous solved problem. This paper found that it is a $\mathbb{NP}$ problem. Furthermore, this paper found that arbitrary $ \mathscr{P} \in \mathbb{P}$ shall have a one-way running graph $G$, and have a corresponding $\mathscr{Q} \in \mathbb{NP}$ 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 $\mathscr{P}$ 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 $\mathbb{NP}$, which does not have a general, deterministic and polynomial time-complexity algorithm, i.e., $\mathbb{P} \neq \mathbb{NP}$. Moreover, this paper pointed out that this theorem actually is an impossible trinity. |
| title | The Radical Solution and Computational Complexity |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2405.15790 |