zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
On the intractability of Hilbert’s Nullstellensatz and an algebraic version of “$NP\neq P$?”. (English) Zbl 0882.03040
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:{\bold C}^n\to{\bold C}$, and complex polynomials of degree $d_i$, $i=1,\dots,\ell$, decide if there is a $z\in{\bold 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:{\bold C}^m\to{\bold C}$, $i=1,\dots,\ell$ with the property $$\sum^\ell_{i=1} g_if_i= 1.\tag{$*$}$$ {\it 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 {\it 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 ${\bold 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 ${\bold C}$. This may be expressed in the present setting as $$T(f)\le 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 ${\bold C}$ which decides the Hilbert nullstellensatz. An algebraic version of the computer science problem “$\text{NP}\ne\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 ${\bold C}$”. It follows that “$\text{NP}\ne\text{P}$ over ${\bold C}$” if and only if our main conjecture is true. In other words, we may assert that the algebraic version of $\text{NP}\ne\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)\le(\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}\ne\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{\bold N}\times{\bold N}\times{\bold 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 ${\bold C}$, then there is a machine $\cal M$ over ${\bold C}$ and a constant $c$ such that $\cal M$ decides twenty questions in time bounded by $(\log k)^c$. Theorem 2. If a machine over ${\bold 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.

MSC:
03D15Complexity of computation
14A05Relevant commutative algebra
11U05Decidability related to number theory
68Q25Analysis of algorithms and problem complexity
68W30Symbolic computation and algebraic computation
WorldCat.org
Full Text: DOI
References:
[1] L. Blum, M. Shub, and S. Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines , Bull. Amer. Math. Soc. 21 (1989), no. 1, 1-46. · Zbl 0681.03020 · doi:10.1090/S0273-0979-1989-15750-9
[2] W. D. Brownawell, Bounds for the degrees in the Nullstellensatz , Ann. of Math. (2) 126 (1987), no. 3, 577-591. JSTOR: · Zbl 0641.14001 · doi:10.2307/1971361 · http://links.jstor.org/sici?sici=0003-486X%28198711%292%3A126%3A3%3C577%3ABFTDIT%3E2.0.CO%3B2-F&origin=euclid
[3] F. Cucker, M. Shub, and S. Smale, Separation of complexity classes in Koiran’s weak model , to appear in Theoret. Comput. Sci. · Zbl 0819.68053 · doi:10.1016/0304-3975(94)00069-7
[4] J. Heintz, On the computational complexity of polynomials and bilinear mappings: A survey , Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Menorca, 1987), Lecture Notes in Comput. Sci., vol. 356, Springer-Verlag, Berlin, 1989, pp. 269-300. · Zbl 0678.68036
[5] J. Heintz and J. Morgenstern, On the intrinsic complexity of elimination theory , J. Complexity 9 (1993), no. 4, 471-498. · Zbl 0835.68054 · doi:10.1006/jcom.1993.1031
[6] W. de Melo and B. F. Svaiter, The cost of computing integers , to appear in Proc. Amer. Math. Soc. JSTOR: · Zbl 0851.11054 · doi:10.1090/S0002-9939-96-03173-5 · http://links.jstor.org/sici?sici=0002-9939%28199605%29124%3A5%3C1377%3ATCOCI%3E2.0.CO%3B2-R&origin=euclid
[7] C. G. Moreira, On asymptotic estimates for arithmetic cost functions , · Zbl 0889.11045 · doi:10.1090/S0002-9939-97-03583-1
[8] M. Shub, Some remarks on Bezout’s Theorem and complexity theory , From Topology to Computation: Proceedings of the Smalefest (Berkeley, CA, 1990) eds. M. W. Hirsch, J. E. Marsden, and M. Shub, Springer-Verlag, New York, 1993, pp. 443-455. · Zbl 0811.13021
[9] L. G. Valiant, Completeness classes in algebra , Conference Record of the Eleventh Annual ACM Symposium on Theory of Computing (Atlanta, Ga., 1979), ACM, New York, 1979, pp. 249-261.