On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?''
type: Item
instance of: scholarly article
title: On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?''
zbMATH Open document ID: 0882.03040
DOI: 10.1215/S0012-7094-95-08105-8
author: Michael Shub
author: Stephen Smale
published in: Duke Mathematical Journal
publication date: 1996-06-24T00:00:00Z
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{…
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 14A05
Mathematics Subject Classification ID: 11U05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 880069
zbMATH Keywords: intractability
zbMATH Keywords: Hilbert nullstellensatz
zbMATH Keywords: algebraic algorithms
zbMATH Keywords: decision algorithm
zbMATH Keywords: polynomial time algorithm
Wikidata QID: Q56697964
MaRDI profile type: Publication
cites work: On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
cites work: Bounds for the degrees in the Nullstellensatz
cites work: Separation of complexity classes in Koiran's weak model
cites work: Q3835021
cites work: On the intrinsic complexity of elimination theory
cites work: The cost of computing integers
cites work: On asymptotic estimates for arithmetic cost functions
cites work: Q4279734
full work available at URL: s0012-7094-95-08105-8
OpenAlex ID: W2082560626
description: scientific article; zbMATH DE number 880069