On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``NP P?

Complexity of computation (including implicit computational complexity) (03D15) Decidability (number-theoretic aspects) (11U05) Relevant commutative algebra (14A05) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Review text

We relate an elementary problem in number theory to the intractability of deciding whether an algebraic set defined over the complex numbers (or any algebraically closed field of characteristic zero) is empty. More precisely, we first conjecture: The Hilbert nullstellensatz is intractable. The Hilbert nullstellensatz is formulated as a decision problem as follows. Given \(f_1,\dots,f_\ell:{\mathbf C}^n\to{\mathbf C}\), and complex polynomials of degree \(d_i\), \(i=1,\dots,\ell\), decide if there is a \(z\in{\mathbf C}^m\) such that \(f_i(z)= 0\) for all \(i\). There is an algorithm for accomplishing this task. From Hilbert, the answer is no if and only if there are polynomials \(g_i:{\mathbf C}^m\to{\mathbf C}\), \(i=1,\dots,\ell\) with the property \[ \sum^\ell_{i=1} g_if_i= 1.\tag{\(*\)} \] \textit{W. D. Brownawell} [Ann. Math., II. Ser. 126, 577-591 (1987; Zbl 0641.14001)] has made the most decisive next step by finding a good bound on the degrees of these \(g_i\). With that, one may decide if \((*)\) has a solution by linear algebra, since \((*)\) is a finite-dimensional linear system with the \(g_i\)'s as unknowns. This procedure is called the ``effective nullstellensatz. To say what ``intractable means in our conjecture, it is necessary to have a formal definition of algorithm in this context. That is done in a joint paper of \textit{L. Blum} and the authors [Bull. Am. Math. Soc., New Ser. 21, 1-46 (1989; Zbl 0681.03020)]. In that paper, algebraic algorithms (called algorithms over \({\mathbf C})\) are described in terms of ``machines, which make arithmetical computations and branch according to whether a variable (the first state variable) is zero or not. In the paper of Blum and the authors [loc. cit.], furthermore, one has the concept of a polynomial time algorithm, in particular, a polynomial time decision algorithm over \({\mathbf C}\). This may be expressed in the present setting as \[ T(f)\leq s(f)^c\qquad (\text{the }c\text{ power of }s(f)\text{ all }f). \] Here \(f= (f_1,\dots,f_\ell)\) is the input, \(T(f)\) is the number of operations (arithmetic, branching) used to accomplish the decision, and \(s(f)\) is the total number of coefficients of the \(f_i\) (input size). Also \(c\) is a universal constant. The input size is \[ s(f)= \sum^\ell_{i=1} {m+d_i\choose d_i}. \] Our conjecture is now formally the mathematical statement: There is no polynomial time algorithm over \({\mathbf C}\) which decides the Hilbert nullstellensatz. An algebraic version of the computer science problem ``\(\text{NP}\neq\text{P}\)? is also introduced in the cited paper of Blum and the authors. From that paper, it follows that the nullstellensatz is a universal decision problem in a certain sense. It is ``NP complete over \({\mathbf C}\). It follows that ``\(\text{NP}\neq\text{P}\) over \({\mathbf C}\) if and only if our main conjecture is true. In other words, we may assert that the algebraic version of \(\text{NP}\neq\text{P}\) is true if and only if the Hilbert nullstellensatz is intractable. Given a sequence of integers \(a_k\), we say that \(a_k\) is easy to compute if there is a constant \(c\) such that \(\tau(a_k)\leq(\log k)^c\), all \(k>2\), and is hard to compute otherwise. We say that the sequence \(a_k\) is ultimately easy to compute if there are nonzero integers \(m_k\) such that \(m_ka_k\) is easy to compute and ultimately hard to compute otherwise. Main Theorem. If the sequence of integers \(k!\) is ultimately hard to compute, then the Hilbert nullstellensatz is intractable, and consequently the algebraic version of ``\(\text{NP}\neq\text{P}\) is true. To prove the Main Theorem, we consider an intermediate decision problem which we call twenty questions: \[ \text{Input}\qquad (k,ht(k),z)\in{\mathbf N}\times{\mathbf N}\times{\mathbf C}. \] \[ \text{Decide if}\quad z\in\{1,2,\dots,k\}. \] Here \(ht(k)\) is defined to be the largest natural number less than or equal to \(\log k\). Theorem 1. If the Hilbert nullstellensatz is tractable, i.e. if \(\text{NP}=\text{P}\) over \({\mathbf C}\), then there is a machine \(\mathcal M\) over \({\mathbf C}\) and a constant \(c\) such that \(\mathcal M\) decides twenty questions in time bounded by \((\log k)^c\). Theorem 2. If a machine over \({\mathbf C}\) decides twenty questions in time bounded by \((\log k)^c\) for some constant \(c\), then the sequence \(k!\) is ultimately easy to compute. The Main Theorem follows immediately from Theorems 1 and 2.

Recommendations

Cites work

Cited in

(33)

This page was built for publication: On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1913573)