A polynomial-time algorithm for deciding the Hilbert Nullstellensatz over $\mathbb{Z}_2$. A proof of $\mathbf{P}=\mathbf{NP}$ hypothesis
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916364554338304 |
|---|---|
| author | Petrov, Petar P. |
| author_facet | Petrov, Petar P. |
| contents | Let ${\mathbf P}$ be the class of polynomial-time decision problems and $\mathbf{NP}$ be the class of nondeterministic polynomial time decision problems. We prove the following:
Theorem 3. The classes ${\mathbf P}$ and $\mathbf{NP}$ are equivalent. That is, ${\mathbf P}=\mathbf{NP}$. Theorem 3 gives a positive answer to the question $$\hbox{Does }{\mathbf P}=\mathbf{NP}?,$$ see S. Cook, The $\mathbf{P}$ versus $\mathbf{NP}$ problem, Official problem description, www.claymath.org/millennium-problems. Crucial for its proof is Theorem 2, from which it follows that the $\mathbf{NP}$-complete problem of deciding the Hilbert Nullstellensatz over $\mathbb{Z}_2$ belongs to the class ${\mathbf P}$.
Theorem 2. There is a constructive algorithm for deciding the Hilbert Nullstellensatz over $\mathbb{Z}_2$, where $\mathbb{Z}_2$ is the space of all complex numbers with integer real and imaginary parts. The number $s(n,m_σ)$ of basic steps of the algorithm, where $n$ is the number of variables and $m_σ$ is the total length of input polynomials, satisfies the inequality \begin{eqnarray*} & & s(n,m_σ) \\ & \le & c_2\{m_σ^2\log m_σ+\min\{[m_σ^{(1)}]^3,(d_1)^3\}+\sum_{\ell =1}^{n-2}N^{(l)}\min\{[m_σ^{(\ell +1)}]^2,(d_{\ell +1})^2)\}\\ && +N^{(n-1)}\min \{m_σ,d_n\} \} \end{eqnarray*} where $c_2$ is an absolute constant, $\{d_{\ell}\}_{\ell=1}^n$ are the maximal partial degrees in $\{z_{\ell}\}_{\ell=1}^n$, respectively, and the numbers $m_σ^{(\ell)}$ and $N^{(\ell)}$ are characteristics of the input polynomials, concerning partial lengths and numbers of major sub-monomials it the natural order of monomials, defined in the body of the paper. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_07327 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | A polynomial-time algorithm for deciding the Hilbert Nullstellensatz over $\mathbb{Z}_2$. A proof of $\mathbf{P}=\mathbf{NP}$ hypothesis Petrov, Petar P. General Mathematics 32A08, 68Q15, 68Q25, 68Q17, 68R07, 68R10, 68T20, 90B10, 90C35 Let ${\mathbf P}$ be the class of polynomial-time decision problems and $\mathbf{NP}$ be the class of nondeterministic polynomial time decision problems. We prove the following: Theorem 3. The classes ${\mathbf P}$ and $\mathbf{NP}$ are equivalent. That is, ${\mathbf P}=\mathbf{NP}$. Theorem 3 gives a positive answer to the question $$\hbox{Does }{\mathbf P}=\mathbf{NP}?,$$ see S. Cook, The $\mathbf{P}$ versus $\mathbf{NP}$ problem, Official problem description, www.claymath.org/millennium-problems. Crucial for its proof is Theorem 2, from which it follows that the $\mathbf{NP}$-complete problem of deciding the Hilbert Nullstellensatz over $\mathbb{Z}_2$ belongs to the class ${\mathbf P}$. Theorem 2. There is a constructive algorithm for deciding the Hilbert Nullstellensatz over $\mathbb{Z}_2$, where $\mathbb{Z}_2$ is the space of all complex numbers with integer real and imaginary parts. The number $s(n,m_σ)$ of basic steps of the algorithm, where $n$ is the number of variables and $m_σ$ is the total length of input polynomials, satisfies the inequality \begin{eqnarray*} & & s(n,m_σ) \\ & \le & c_2\{m_σ^2\log m_σ+\min\{[m_σ^{(1)}]^3,(d_1)^3\}+\sum_{\ell =1}^{n-2}N^{(l)}\min\{[m_σ^{(\ell +1)}]^2,(d_{\ell +1})^2)\}\\ && +N^{(n-1)}\min \{m_σ,d_n\} \} \end{eqnarray*} where $c_2$ is an absolute constant, $\{d_{\ell}\}_{\ell=1}^n$ are the maximal partial degrees in $\{z_{\ell}\}_{\ell=1}^n$, respectively, and the numbers $m_σ^{(\ell)}$ and $N^{(\ell)}$ are characteristics of the input polynomials, concerning partial lengths and numbers of major sub-monomials it the natural order of monomials, defined in the body of the paper. |
| title | A polynomial-time algorithm for deciding the Hilbert Nullstellensatz over $\mathbb{Z}_2$. A proof of $\mathbf{P}=\mathbf{NP}$ hypothesis |
| topic | General Mathematics 32A08, 68Q15, 68Q25, 68Q17, 68R07, 68R10, 68T20, 90B10, 90C35 |
| url | https://arxiv.org/abs/2208.07327 |