论文标题
用于决定Hilbert nullstellensatz $ \ Mathbb {Z} _2 $的多项式时间算法。 $ \ mathbf {p} = \ mathbf {np} $假设的证明
A polynomial-time algorithm for deciding the Hilbert Nullstellensatz over $\mathbb{Z}_2$. A proof of $\mathbf{P}=\mathbf{NP}$ hypothesis
论文作者
论文摘要
令$ {\ mathbf p} $为多项式决策问题类，$ \ mathbf {np} $是非确定的多项式时间决策问题的类。我们证明了以下内容： 定理3。类$ {\ mathbf p} $和$ \ mathbf {np} $是等效的。也就是说，$ {\ mathbf p} = \ mathbf {np} $。定理3给出了问题$$ \ hbox {do} {\ mathbf p} = \ mathbf {np}？，$$请参见S.其证明至关重要的是定理2，从中可以得出$ \ mathbf {np} $ - 在$ \ mathbb {z} _2 _2上确定Hilbert nullstellensatz的完整问题属于类$ {\ Mathbf P} $。 定理2。有一种建设性算法，用于决定Hilbert nullstellensatz在$ \ Mathbb {z} _2 $上，其中$ \ Mathbb {Z} _2 $是所有复杂数字的空间，具有插图真实和想象中的零件。算法的基本步骤的数字$ s（n，m_σ）$，其中$ n $是变量的数量，$m_σ$是输入多项式的总长度，满足不等式\ begin {eqnarray*} m_σ+\ \ {[[m_σ^{（1）}]^3，（d_1）^3 \}+\ sum _ {\ ell = 1}^{n-2} n^{（l）} \ \ min \ min \ min \ min \ {[m_t +1}）^2）\} \\ && +n^{（n-1）} \ min \ {m_σ，d_n \} \ end end {eqnarray*}，其中$ c_2 $是绝对常数，$ \ {d _ {d _ {\ ell} \ ell}在$ \ {z _ {\ ell} \} _ {\ ell = 1}^n $中，以及数字$ $m_σ^{（\ ell）} $和$ n^{（\ ell）} $是输入的一定数量和主要阶段的commials of Monials natural natural of Mon的特征。
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.
