A polynomial-time algorithm for deciding the Hilbert Nullstellensatz over $\mathbb{Z}_2$. A proof of $\mathbf{P}=\mathbf{NP}$ hypothesis

Abstract

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.