How Lower and Upper Complexity Bounds Meet in Elimination Theory

L.M. Pardo ^{∗}^{†}

                     This paper is published in
   Applied Algebra, Algebraic Algorithms and Error Correcting Codes
           Proc.  AAECC-11, Springer LNCS Vol.  9, 1995.

1 Introduction

Computer algebra is a research field that combines two main subjects that were separated for years : algebra and computer science. A short characterization would be : computer algebra deals with the symbolic manipulation of algebraic entities. Thus computer algebra seems to split in so many domains as algebra does, whereas every domain has its own approach to the subject.

These pages are mainly concerned with just one of these domains : elimination over algebraically closed fields. In other words, we discuss some basic problems whose origins come from algebraic geometry and commutative algebra. Because of the obvious limitations of a talk like this we are obliged to omit some related and relevant research domains as elimination over real closed fields or computational number theory. We refer the reader to the surveys [44] or [63].

First of all, the problems we deal with must be located. Properly speaking any algorithm can be considered as the manipulation of algebraic entities. In this sense all the problems in computer science may be easily translated to elementary algebraic geometry. Therefore, one may conclude that computer science is a part of computer algebra.

On the other hand, one can define computer algebra as the field that designs algorithms to solve problems whose original nature is either algebraic or geometric. In this sense the algorithms of computer algebra must be implemented on a machine and computer algebra becomes a part of computer science.

Both considerations imply that computer science and computer algebra deal with the same range of problems. In particular, computer science limitations are also reflected in computer algebra. However, typical algorithms in algebra do not take into account computer science aspects. When running them, computers are overloaded with unnecessary routines and the user from algebra must be patient. Our point of view differs from that of [4].

∗Partially supported by DGICyT PB92–0498–C02–01 and PB93–0472–C02–02.

†Depto. de Matemáticas, Estadística y Computación . F. de Ciencias. Univ. de Cantabria. E–39071 Santander, Spain. pardo@matsun1.unican.es

This phenomenon of practical inefficiency may be analyzed by means of complexity considerations. Complexity research aims to explain the behaviour of computers when dealing with syntactically defined problems. The main goal is to explain why either a program requires more space than the computer disposals or the answer to the input question cannot be expected in reasonable time. This is generally translated to theoretical models that represent a relevant aspect of a concrete computer. The most important theoretical model is the well–established Turing machine model (or any equivalent one). Tractable problems are classified in terms of these complexity estimates (cf. [1], [29]) : problems requiring more than polynomial time are considered intractable. To illustrate what we mean let us consider the following NP– complete problem :

3SAT : Let Φ(X_{1}, …, X_{n}) be a formula of the propositional calculus, given in conjunctive normal form by clauses with 3 literals i.e.

Φ(X_{1}, …, X_{n}) := ⋀_{i=1}^{n} Φ_{i}(X_{i_{1}}, X_{i_{2}}, X_{i_{3}})

Decide whether the formula Φ is satisfiable.

This is a central problem in computer science. It represents the “lightest” class of intractable problems. However, it represents a very particular case of an elimination task in algebraic geometry. There is a straightforward translation of propositional calculus to polynomials over fields of any characteristic. We choose the characteristic 0 case. First, we consider the following system of polynomial equations :

f_{1} = X_{1}^{2} − X_{1}, …, f_{n} = X_{n}^{2} − X_{n}

The set of zeroes {f_{1} = 0, …, f_{n} = 0} = {0, 1}^{n} agrees with the possible True/ False inputs for the formula Φ . Now, the clauses Φ_{i} can be translated to polynomials q_{i} ∈ ZZ[X_{i_{1}}, X_{i_{2}}, X_{i_{3}}] such that for all x ∈ {0, 1}^{n}, Φ_{i}(x) is true if and only if q_{i}(x) ∈ ZZ is odd. This can be done just by replacing boolean operators by their correspondent arithmetic operations. The polynomials q_{i} are three variable polynomials of degree at most three, and coefficients in {0, 1}. Consequently, the formula Φ is satisfiable if and only if there is some point x ∈ {0, 1}^{n} such that for all i, the value q_{i}(x) is an odd integer number. To explicit this transformation let us consider the following polynomial :

f_{n+1} := ∑_{i=1}^{n}(q_{i} − 1)^{2}(q_{i} − 3)^{2}(q_{i} − 5)^{2}(q_{i} − 7)^{2}

The formula Φ is satisfiable if and only if the following algebraic variety is nonempty :

V := {x ∈ C^{n} : f_{1}(x) = 0, …, f_{n}(x) = 0, f_{n+1}(x) = 0}

Then, 3SAT is a particular case of the following problem of algorithmic algebraic geometry :

Weak Nullstellensatz : Given polynomials f_{1}, …, f_{n+1} ∈ ZZ[X_{1}, …, X_{n}] , of degree at most d decide whether the following variety is empty :

V := {x ∈ C^{n} : f_{1}(x) = 0, …, f_{n+1}(x) = 0}  (1)

Up to now, nobody knows whether there is a polynomial time algorithm to solve 3SAT. The input can be written with O(n) bits, while any known optimal algorithm runs in time n2^{n} using O(n) units of memory.

Nevertheless, there exists a current opinion in the context of computer algebra that 3SAT is solvable in polynomial time by means of the specific tools of this domain. Algebraists observe that the input polynomial system has degree 24 in n variables. Best algebraic algorithms for 3SAT run in time n^{O(n)} and require at least 2^{n} units of memory to proceed. This is far from being polynomial in time and machines behave correspondingly. This approach pushes the computer to work in awful conditions. It often stops its computation because it has rapidly spent all memory resources.

Some of these drawbacks are caused by the algebraic setting, whose way of thinking inhibits the design of procedures. An example is the use of data structures as representing polynomials by their coefficients or matrices by their entries. These data structures represent themselves an obstruction to computations which has no counterpart in computer science : an exponential requirement of memory implies an exponential lower bound for the time and no improvement may be expected.

While the example above illustrates the memory requirements, there are other examples where the use of “mathematical” data structures of inputs and outputs inhibit improvements of the algorithms. A typical example is the following

Division Problem in the Nullstellensatz Let assumptions and notations be as in the Nullstellensatz. If the variety V is empty, compute g_{1}, …, g_{n+1} ∈ 0 Q[X_{1}, …, X_{n}] such that the following equality holds

1 = g_{1}f_{1} + ⋯ + g_{n+1}f_{n+1}

The polynomials g_{1}, …, g_{n+1} have typically degree d^{n}. Encoding the g_{i} ’s by their coefficients would require \binom{d^{n}+n}{n} units of memory. This would imply that no expected procedure can solve the Division Problem in less than d^{n^{2}} steps for d >> n.

In other branches of mathematics, a similar phenomenon of obstructions appears too. For instance, the approach of numerical analysis to solving systems of multivariate polynomial equations by means of Newton’s method requires the use of rational numbers of exponential binary length.

It seems that mathematicians prefer a easy–to–recognize representations of mathematical entities. However, such representations may be hard–to–handle and may increase the complexity of algorithms.

This paper presents a survey over alternative methods which have been developped the last years in order to circunvent the phenomenon of obstructions in algebraic and geometric elimination algorithms. A possible way out of the dilemma is encoding of polynomials and integers as programs.

Even if the polynomials g_{i} in the Division Problem are typically of degree d^{n}. they can be represented by programs of length d^{O(n)} . This improvement means that for d ≥ n, the Division Problem runs in exponential time with dense encoding of polynomials whereas it can be solved in polynomial time when the polynomial outputs can be encoded as a program.

Thus we use the fact that polynomials are not only algebraic entities but also functions which can be evaluated and therefore we can think in encoding polynomials as programs evaluating functions. The encoding of polynomials we shall choose for the purpose of this expositiomn is that of straight–line programs (a tool generally used in algebraic complexity thoery for the modelization of semi–numerical algorithms). Doing this we face a certain duality phenomenon : programs in computer algebra are also inputs, outputs and intermediate results. Our idea is not new : it appears behind the notion of the Universal Turing machine or behind programming languages as LISP.

An alternative, radical solution of the dilemma would be a proof that no way out from exponential complexity is possible. This leads to the research of lower complexity bounds. We also survey the attempts and their up to date success. It is remarkable that analysis of obstructions suggest alternatives for improvements. The paper ends with a comparison of both upper and lower complexity bounds for geometric elimination problems.

Contents

1 Introduction 1

2 The Problem and the Model 5

2.1 Semantics of the Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1 The Context of Algebraic Geometry and Commutative Algebra… 7 2.1.2 The Context of Numerical Analysis. . . . . . . . . . . . . . . . . . . 9

2.2 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.1 Polynomials. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.2 Integer Numbers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.3 Manipulating these Data Structures . . . . . . . . . . . . . . . . . . . . . . 15 2.3.1 Arithmetic operations. . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3.2 Equality tests. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.4 Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3 Lower Bounds 18 3.1 Dense Encoding of Inputs and Outputs . . . . . . . . . . . . . . . . . . . . 19 3.2 Sparse Encoding of Inputs and Outputs . . . . . . . . . . . . . . . . . . . . 19 3.3 Program Encoding of Inputs and Outputs . . . . . . . . . . . . . . . . . . . 20 3.4 Numerical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.5 Final Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4 Upper Bounds 24 4.1 Dense Encoding of Inputs and Outputs . . . . . . . . . . . . . . . . . . . . 25 4.2 Dense Encoding of Inputs and Program Encoding of Outputs . . . . . . . . 26 4.3 Program Encoding of Inputs and Outputs . . . . . . . . . . . . . . . . . . . 28 4.4 Final comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5 References 30

2 The Problem and the Model

The aim of these pages is to discuss by means of concrete examples the general problem of the complexity of algorithms which solve mathematical problems. There are two sides of such a mathematical problem : the semantical and the syntactical sides. The semantical aspect can be understood as the mathematical meaning of “solution”. The syntactical side deals with the representation and handling of mathematical entities.

Usually complexity estimates depend only on the syntactical side of the problem. Semantical incidence on complexity comes mainly through the syntactical side. The mathematical context has some established prejudices to represent their mathematical entities. This sometimes yields an obstruction to improvements.

By the analysis of the syntactical aspect we explain the concrete behaviour of a real computer that solves the problem. We require that inputs and outputs are representable over a finite alphabet, {0, 1} for instance. They are encoded as finite sequences of symbols of the alphabet, i.e. words in {0, 1}^{∗} = ∪_{n∈IN} {0, 1}^{n}. If x ∈ {0, 1}^{N} is such a word we say that x has length N . Following Church’s thesis, an algorithm is a Turing machine. In our discussion, a Turing machine has a read–only input tape, a finite number of work tapes and a distinguished output tape (cf. [1] for a more detailed description).

This exposition is devoted to worst–case complexity estimates. Worst case estimates for a given algorithm, a Turing machine or a problem are functions S, T : IN ⟶ IN , with the following interpretation :

• T (N) , the time required by the machine on inputs of length N .

• S(N) , the work space (maximum length of words written in the work tapes) which the algorithm uses for inputs of length N .

Intuitively speaking, the input length can be understood as the time required by a typewriter to print the input under some chosen encoding. Most commonly used functions are N^{O(1)} (polynomial estimates), 2^{O(N)} (exponential estimates) and 2^{O(N^{2})} (doubly exponential estimates). Thus, structural complexity classifies problems in terms of these estimates, and describes the following central complexity classes :

The first one is the class of tractable problems (i.e. those problem that are solvable by a real computer in a reasonable period of time). This is the class P of problems solvable in deterministic polynomial time ( T (N) := N^{O(1)} ). Next we have the classes of softer intractable problems : those problems that are not known to be polynomial time solvable, but whose memory requirements are still polynomial. There is a current opinion in computer science that problems requiring more than polynomial space to be solved have no interest for practical computing.

These problems are mainly represented by two classes : the class NP of problems solvable by a non–deterministic polynomial time procedure ( non–deterministic procedures with T (N) := N^{O(1)} ) and the class PSPACE of problems solvable using a polynomial amount of space (i.e. S(N) := N^{O(1)} ). It is known that the following inclusions hold : P ⊆ NP ⊆ PSPACE; but nobody knows whether any of these inclusions is strict.

The following classes in the hierarchy represent strongly intractable problems (i.e. those problems for which no polynomial time algorithm exists). They are mainly represented by the classes of exponential time procedures EXTIME (i.e. T (N) := 2^{O(N)} ) and doubly exponential time procedures DEXTIME (i.e. T (N) := 2^{O(N^{2})} ). As for space the classes up to EXPSPACE of exponential expace requirements (i.e. S(N) := 2^{O(N)} ).

There are some known facts relating these classes :

Theorem 1 (cf. [1] )

• Time bounds imply space bounds.

• Non–determinism is not relevant for space estimates.

• Time and Space Hierarchy Theorems : The following inclusions are strict :

P ⊂ EXT IME ⊂ DEXT IME
P SP ACE ⊂ EXP SP ACE.

There is another class of relative importance : the class of bounded error probabilistic polynomial time procedures ( BPP). This means that algorithms run non–deterministically making a polynomial number of guessings. In the procedure accepts the input the answer is correct. However, in case of rejection the answer may be true or false with small probability of error. The practical performance of BPP algorithms is very high. The complexity class BPP lays is between P and NP and nobody knows whether it equals any of these classes.

All these relations are represented by the following diagram (here arrow means inclusion) :

⟶ EXTIME ⟶ NEXTIME ⟶ DEXTIME

P {↗ \atop ↘} ↘

BPP ⟶ NP ⟶ PSPACE ⟶ EXPSPACE

while P represents the class of tractable problems, the class of almost tractable problems (i.e. those having some interest for practical computing) is represented by the lower part of the diagram :

P ↘

BPP ⟶ NP ⟶ PSPACE

The classes of the following diagram are considered as strongly intractable problems :

EXTIME ⟶ NEXTIME ⟶ DEXTIME

↘

EXPSPACE

There is another parameter of special importance : the output length. This is the space necessary to write down the output on the corresponding tape. Output length can be interpreted as external memory requirement and represents a lower bound for time.

The fundamental problem we shall consider is roughly speaking that of solving a system of polynomial equations. Thus, our input is always a finite set f_{1}, …, f_{s} ∈ ZZ[X_{1}, …, X_{n}] of multivariate polynomials. The output may depend on the mathematical context. A given input gives rise to many different problems (questions) and to correspondingly many different outputs. Whereas inputs are now fixed we are going to define what a solution means within the contexts of :

• Classical Algebraic Geometry and Commutative Algebra (or schemes).

• Numerical analysis.

2.1 Semantics of the Problem

2.1.1 The Context of Algebraic Geometry and Commutative Algebra.

Both are easily explained by associating to the input polynomials f_{1}, …, f_{s} in the ring ZZ[X_{1}, …, X_{n}] which are supposed of degree at most d, two mathematical entities :

• The ideal generated by these polynomials, i.e. I := (f_{1}, …, f_{s}) :

I := {g ∈ 0 Q[X_{1}, …, X_{n}] : ∃g_{1}, …, g_{s} ∈ 0 Q[X_{1}, …, X_{n}], g = g_{1}f_{1} + ⋯ + g_{s}f_{s}}

• The algebraic variety given as the set of common zeros of f_{1}, …, f_{s} in an algebraic closure of 0 Q , say :

V := {x ∈ C^{n} : f_{1}(x) = 0, …, f_{s}(x) = 0}

According to [62] we speak of geometric properties when refering the algebraic variety and of algebraic properties when refering to the ideal. Two examples of the different approaches may be the following :

• Membership Problem in Polynomial ideals (algebraic) Assume that the input contains besides the the fixed polynomials f_{1}, …, f_{s} an additional polynomial g ∈ ZZ[X_{1}, …, X_{n}] . Decide whether g is in the ideal generated by f_{1}, …, f_{s} in 0 Q[X_{1}, …, X_{n}] . If this is the case, find g_{1}, …, g_{s} ∈ 0 Q[X_{1}, …, X_{n}] such that the following equality holds :

g = g_{1}f_{1} + ⋯ + g_{s}f_{s}

• Strong Nullstellensatz Problem (geometric approach) For the same inputs above, decide whether g vanishes on the variety V .

With respect to the outputs there is a substantial difference between these two problems. Whereas the Strong Nullstellensatz Problem is a decision problem, the output of the Membership Problem may contain polynomials. The output for the first problem is just one bit (the YES or NO answer) as for the second the polynomials have to be adequately represented and they will possibly require a big amount of memory space to be stored (or printed out). Another geometric question with similar simple outputs is that of :

• Noether Normalization Problem for Varieties (geometric) Compute the dimension of the variety V and find a linear change of coordinates such that the new variables are in Noether position with respect to V .

The dimension of V is a number between −1 ( when V is the empty set) and n and a Noether normalization can be represented by a non–singular n × n matrix over ZZ . Again the encodings of these outputs will be rather short. We shall come back to the role played by the output length in the complexity analysis of algorithms.

There is a language which allows a unified description of such questions (and answers and anything related) both from the algebraic as well from the geometric point of view : the language of schemes. This language tends to restate anything we can imagine to be relevant for our subject in terms of coherent sheaves. This terminology may be boiled down in our (generally affine) case to noetherian algebras and modules. Let us illustrate this in a concrete, but also important case. In order to simplify things, assume that s = n holds and that f_{1}, …, f_{n} form a regular sequence in 0 Q[X_{1}, …, X_{n}] . Thus, we can rewrite our problem from the algebraic as well as from the geometric point of view in the following terms :

• The algebraic point of view focusses on the following finite 0 Q− algebra associated to our input system of equations :

A := 0 Q[X_{1}, …, X_{n}]/(f_{1}, …, f_{n})

• The geometric point of view considers mainly the reduced and finite dimensional

0 Q− algebra :

A_{red} := 0 Q[X_{1}, …, X_{n}]/\sqrt{(f_{1}, …, f_{n})}

where \sqrt{(f_{1}, …, f_{n})} denotes the radical of the ideal (f_{1}, …, f_{n}) .

In these terms every approach describes its respective algebra. They are seen as finite dimension 0 Q− vector spaces and also 0 Q[X_{1}, …, X_{n}]− modules. Both algebraic qualities (vector space and module) are enough to completely determine both A and A_{red} and also to solve the polynomial system. Thus, one looks for a basis as 0 Q− vector space and some tensor matrices M_{X_{i}} that represent the multiplication by X_{i}.

As a first comparison, observe that the dimension of A as 0 Q− vector space is typically equal to the Bézout number : d^{n}. However, the dimension of A_{red} is the number of points of V (i.e. the affine degree as in [42]). This is because the algebra A contains more information about the polynomial system than the algebra A_{red}. This can be highlighted comparing the algebras A and A_{red} for the input system f_{1} := X_{1}^{2}, …, f_{n} := X_{n}^{2} . The algebra A conserves the information about the multiplicity of the input ideal with respect to its (unique) associated prime component (X_{1}, …, X_{n}) and its dimension as 0 Q –vector space is 2^{n}, whereas the dimension of A_{red} is simply 1 . Generally we will find that more information in the output requires more memory when running the procedure. This yields an exponential ( 2^{n}) time lower complexity bound to write a monomial basis of A. For this specific type of output, no improvement of the algorithm is possible beyond this time limit.

Coming back to the general statement of the problem, we remark that up to date any procedure that describes the algebraic structure of A produces a list of monomials of 0 Q[X_{1}, …, X_{n}] (typically of cardinality d^{n}) that represents a basis of A as 0 Q− vector space. This is usually called a “monomial basis” of A. On the other hand, the description of A_{red} admits an interesting alternative approach : there are generically many linear forms u ∈ ZZ[X_{1}, …, X_{n}] that separates the points of the variety V (i.e. they satisfy u(x) ≠ u(y), ∀x, y ∈ V ). This linear form u represents in a straightforward manner a basis of A_{red} as 0 Q− vector space : namely, such a basis is given by the images in A_{red} of the set of forms {1, u, …, u^{D−1}}, where D := deg(V) is the (affine) degree of V . We cal u a primitive element of A_{red} (see [34], [56] for more details). Finally, we obtain a representation of A_{red} as a quotient of 0 Q[T] modulo some principal ideal (generated by the minimal polynomial of u) :

A_{red} = 0 Q[X_{1}, …, X_{n}]/(P (u), ρX_{1} − v_{1}(u), …, ρX_{n} − v_{n}(X_{n})) = 0 Q[T]/(P (T))

where ρ is a non-negative integer and v_{1}, …, v_{n}, P ∈ ZZ[T] , being P the minimal polynomial of u in A_{red} and the degree of the v_{i} ’s is at most deg(P) = D. Thus, the geometric output is simply given by a set of univariate integer polynomials of degree at most D and an integer ρ ∈ ZZ . The tensor matrices can be easily obtained from this information : if M is the companion matrix of P (T) , M_{X_{i}} := ρ^{−1}v_{i}(M) . These tensor matrices M_{X_{i}} are not necessarily written and it seems to be an advantage.

The geometric output depends on the set of zeros and it is an open door for improvements. The algebraic output does not distinguish good input systems from ill–conditioned ones : it seems to be handicapped by the output length.

Another problem of central importance in the algebro–geometric context is that of

Elimination : Given a polynomial f_{n+1} , compute the image f_{n+1}(V) .

2.1.2 The Context of Numerical Analysis.

This framework wants to approximate solutions of polynomial systems of equations. We can also assume that s = n and that we have polynomials f_{1}, …, f_{n} ∈ ZZ[X_{1}, …, X_{n}] . What the numerical analysis wants is an approximation, a := (a_{1}, …, a_{n}) , of an isolated point α ∈ V . Observe that if the computer must output a, it has to be represented over a finite alphabet again. Thus, it is natural to restrict our outputs to numbers in 0 Q[i] , where i^{2} = −1 (or similar computable fields). In this case, the final goal agrees with that of diophantine approximation of algebraic numbers.

Given the system f_{1} = 0, …, f_{n} = 0 and ε > 0 , find a ∈ 0 Q[i]^{n} close to some isolated solution α ∈ C^{n} of the system :

|| α − a ||< ε

This is the approach in [89] and [90]. These papers start by defining the following Newton operator : given f := (f_{1}, …, f_{n}) ∈ ZZ[X_{1}, …, X_{n}] , let Df(x) be the jacobian matrix at x which is supossed to be non–singular. Let us define

N_{f}(x) := x − Df(x)^{−1}f(x)

Thus, an “approximate zero” of the system is a point x_{0} ∈ C^{n} such that the sequence

x_{0}, x_{1} := N_{f}(x_{0}), x_{2} := N_{f}(x_{1}), …, x_{n} := N_{f}(x_{n−1}), …  (2)

converges. In this case the sequence converges to some “authentic” zero of the system. A priori an “approximate zero” does not need to be a proximate zero. Nevertheless, if x_{0} is an “approximate zero”, the convergence of the sequence 2 is quadratic.

Theorem 2 ([89]) Let notations be as above. Then, for any n ∈ IN the following inequality holds :

|| x_{n+1} − x_{n} ||< (\frac{1}{2})^{2^{n}−1} || x_{1} − x_{0} ||

Moreover, there is some α ∈ V such that for any n ∈ IN the following holds :

|| x_{n} − α ||< (\frac{1}{2})^{2^{n}} || x_{0} − α || .

In practice this means that we can get close to some root α of the system very fast. The characterization and construction of “approximate zeros” plays an important role in the numerical analysis approach to polynomial system solving (cf. [90] and the references given there).

2.2 Syntax

The input length is the parameter for complexity estimates. The output length is a lower bound for the time. Complexity statements sensibly depend on the way mathematical entities are encoded, i.e. from the data structurte we use. Once the encoding is fixed, the algorithm represented by a Turing machine runs using its own elementary operations : read, write ( a single symbol in {0, 1}), and move (a single step either left or right). Thus, we have to describe how our data structure is manipulated in order to simulate mathematical operations.

In order to elucidate what “manipulating data structures” and “simulating mathematical operations” means, let us recosnider the 3SAT problem from a more algebraic point of view. As the polynomials X_{1}^{2} − X_{1}, …, X_{n}^{2} − X_{n} form a Gröbner basis of the radical ideal they generate with respect to lexicographic ordering, both the algebras A and A_{red} above agree. We have the obvious monomial basis of the 0 Q− algebra

0 Q[X_{1}, …, X_{n}]/(X_{1}^{2} − X_{1}, …, X_{n}^{2} − X_{n})

and the tensor matrices M_{X_{i}} are known. Thus, with the notations of Section 1, let us consider the matrix

M := f_{n+1}(M_{X_{1}}, …, M_{X_{n}})

We observe that the formula Φ is satisfiable if and only in the determinant of M is zero. If we represent all these algebraic objects occuring in this argument by their usual encoding (e.g the matrices as a list of entries) we need space of size 2^{n} to run the procedure. This is impracticable in “real life”.

However, the matrices M_{X_{i}} are very special. They have at most one non-zero coordinate at every row. It is easy to write a program that for inputs (k, l) outputs the (k, l)− coordinate of M_{X_{i}}. There are at most n programs of constant size that do this task. Now, let us write a program that evaluates f_{n+1}(M_{X_{1}}, …, M_{X_{n}}) . Then, let us write a program that computes the determinant (as that of [7]). In this way one encodes the determinant of M as a program (a Turing machine), whose output is det(M) . The space required to save this program is O(n) . In this way the original computer algebra algorithm to solve 3SAT is translated into a more computational problem : decide whether this very particular program – of length O(n) – evaluates the integer number 0 or not. The procedure is deterministic and requires exponential time; but the memory space is reduced to O(n) . A general procedure for such elimination problem that focusses an economy of space can be found in [67]. Our example approximates us to computer science maintaining the line of computer algebra context.

In elimination one has to encode polynomials and integers. We are now going to see how these mathematical objects are usually encoded in the literature of elimination.

2.2.1 Polynomials.

A polynomial is a syntactical object and defines an holomorphic mapping between two affine spaces (the polynomial mapping f : C^{n} ⟶ C). The difference between polynomials (or rational functions) and other holomorphic (or meromorphic) functions is that there are procedures which allow effectively evaluate the function at every point where it is defined. A straightforward way to evaluate a polynomial in a point consists in first evaluating all monomial terms occuring in the polynomial in the given point and then adding the results up. It was observed long ago that this is not the only way to evaluate a polynomial in a given point. For instance Newton mentions in 1667 the expression :

\overline{\overline{\overline{y − 4} × y : +5} × y :: −12} × y : +17

which in nowadays language means (((y − 4)y + 5) − 12) y + 17 (cf. [75]).

Polynomials have two main syntactical components : one is combinatorial (monomials, degree, number of variables, program, etc.) the second has an algebraic nature (the ground ring or field). The balance between both components would determine part of the performance of the encoding. This gives rise to three main levels :

• Dense encoding.

• Sparse/Fewnomials encoding.

• Program encoding.

It is remarkable that when we focus on the “semantical” aspect of polynomial (i.e. we think polynomials as mappings), the combinatorial component may also be augmented.

The following encodings are described in descent, every time we increase the weight of the combinatorial part, we are getting closer of the model for practical computing : the Turing machine model.

Dense Encoding. This encoding does not care about the combinatorial component : polynomials are simply represented a list of coefficients. In some sense, polynomials are viewed as words over the alphabet given by the ground ring, i.e.

R[X_{1}, …, X_{n}] = R^{∗}

For instance such a representation can be realized by a recursive pointer given by a monomial order in R[X_{1}, …, X_{n}] . This is the idea behind data structures in solving of polynomial equation systems by rewriting techniques (Göbner basis methods; for short : Gröbner solving). This kind of encodings is usually manipulated by algebraic computation models making arithmetic operations (addition, substraction, multiplication or division of elements of R. Eventually, when decisions are involved, we have to add to the arithmetic operations equal–to–zero tests). This type of computation models comes up with the operations of linear algebra techniques. The so called BSS–model of [11] (if its use of arbitrary complex numbers is forgiven by the reader, cf. also [23], and the cost of arithmetic operations is also counted) seems to be very accurate for this purpose.

Two mathematical parameters are commonly used in order to measure the size of a polynomial given by its dense encoding : degree and number of variables. Thus, the dense encoding of a polynomial f ∈ R[X_{1}, …, X_{n}] of degree at most d has length :

\binom{d + n}{n} = \binom{d + n}{d}

This quantity can be estimated by d^{n} for d ≥ n and n^{d} for n ≥ d. If d << n, d = 2 for instance, a procedure that runs in time d^{O(n)} behaves on a real computer as an exponential time procedure. Usually, computer algebra procedures prefers to assume d ≥ n and in this case procedures that run in time d^{O(n)} are cconsidered polynomial time procedures.

Sparse Encoding. A little bit closer to the Turing machine pattern is that of sparse encoding of polynomials. Polynomials are given as a list of pairs (μ, a_{μ}) , where μ ∈ IN^{n} is a multi–index, encoded in binary, and a_{μ} ∈ ZZ . Here, the boolean part plays some additional role, and many efforts have been done to relate combinatorial objects to polynomials. A meaningful example is that of Newton polytopes (cf. [10],[41], [98], [99],[100] and the references therein). Unfortunately this approach has some inconvenients. Essentially, the condition of being sparse is not stable under simple geometric operations as a linear change of variables. Moreover, the complexity estimates obtained up to now from this approach are not very promising.

Program Encoding. The different options to evaluate concrete polynomials can be realized as programs. Such programs are also encodings of the concrete polynomial : we can recover the coefficients if wanted (interpolating at many points). As it has been remarked this is not always necessary.

The idea in elimination is to compress the polynomials as programs where the elementary operations are those of a ring (or field) : {+, −, ×}. These elementary operations are organized as the path someone follows in order to evaluate the polynomial (a directed acyclic graph). Both components (the directed acyclic graph and the arithmetic operations) form a straight–line program.

The straight–line program set up started as semi–numerical algorithm modelling (cf. [54], [97]). At the beginning there was a question of A.M. Ostrowski in 1954 : Is Newton– Horner’s rule optimal? (cf. [76]). Since then, algebraic complexity theory had a relevant development, mainly concerned with lower bound estimates for polynomial evaluation and the membership problems to constructible sets. It is not the purpose of these pages to make a survey of what has been done in this area of research. We refer the reader to the following surveys on the subject :[97], [43], [32], [40], [14].

The straight–line program approach is studied in computer algebra since the beginning of the eighties. Several authors independently discovered that straight–line programs may play some important role in elimination. They all considered only univariate elimination, trying to obtain the maximum benefit from this encoding. Among them we can quote here the following : J. Heintz, O.H. Ibarra, E. Kaltofen, S. Moran, J. Morgenstern, C.P. Schnorr , J.T. Schwartz, M. Sieveking, R. Zippel. Not all the ideas at that moment were published, but there are several papers to quote : [47], [48], [51], [52], [53], [86], [102].

A straight–line program Γ over ZZ is a pair Γ = (G, Q) , where G is a directed acyclic graph and Q is an assignment of instructions to the gates of the graph. There are n + 1 gates of indegree 0 identified with the variables X_{1}, …, X_{n} and the constant 1 . They are called the input gates of G. We define the depth of a gate ν of our graph as the length of the longest path joining ν with some input gate. Let us denote the gates of the directed acyclic graph by pairs of integer numbers (i, j) , where i represents the depth of the gate and j is the corresponding value of an arbitrary numbering imposed to the set of gates of depth i (this encoding can be seen, for instance, in [59] or [71]).

The arithmetic gates have the following form :

Q_{i,j} := ( ∑_{0≤r≤i−1} A_{r,s}Q_{r,s})( ∑_{0≤r′≤i−1} B_{r′,s′}Q_{r′,s′})

where A_{r,s}, B_{r′,s′} ∈ {−1, 0, 1} ⊆ ZZ are called the parameters, and Q_{r,s}, Q_{r′,s′} are precomputed results. When evaluation over a field is considered, the division {/} is added. Thus, it evaluates rational functions in 0 Q(X_{1}, …, X_{n}) . Those straight–line program that contain no division are usually called division free straight–line programs.

We estimate the straight–line program by means of two distinguished elements :

• The size of the straight–line program, given by the number of gates of the graph G.

• The non–scalar depth of the straight–line program, given as the maximum depth of all gates in the graph.

In terms of complexity, the size is associated to the sequential time, while the depth is associated to the parallel time. Thus, a well–parallelizable straight–line program is one whose non–scalar depth is logarithmic in the size.

Observe that a straight–line program of size L we can evaluate at most 3^{O(L^{2})} different polynomials. In [59] the following estimate is shown :

Lemma 3 Let p = ∑_{ν} a_{ν}X_{1}^{ν_{1}} ⋯ X_{n}^{ν_{n}}ZZ[X_{1}, …, X_{n}] be a polynomial which can be evaluated by a straight–line program Γ of size L and non–scalar depth ℓ. Then, the following holds :

• The degree of p is at most 2^{ℓ}.

• The weight of the polynomial p, w(p) , is bounded by

w(p) := ∑_{ν∈IN^{n}} | a_{ν} |≤ L^{2^{ℓ+1}−1}  (3)

From this lemma one easily concludes that given p and given a = (a_{1}, …, a_{n}) ∈ ZZ^{n}, h = max{log_{2} | a_{1} |, …, log_{2} | a_{n} |}, a Turing machine simulates the procedure which evaluates p(a) in time and space of order 2^{O(ℓ)}(Lh)^{O(1)} . In case of well–parallelizable straight–line programs, this bound is of order (Lh)^{O(1)} .

The encoding of a polynomial p is the directed acyclic graph, whose gates are encoded as a list :

((i, j), (A_{r,s} : 0 ≤ r ≤ i − 1), (B_{r′,s′} : 0 ≤ r′ ≤ i − 1))

where (i, j) is the encoding of the gate, and the parameters A_{r,s}, B_{r′,s′} are in {−1, 0, 1}. It is clear that a straight–line program of size L can be encoded in O(L^{2}) units of memory.

The straight–line program encoding is the one with biggest combinatorial component among those in the literature of Elimination; but this is not the last step and improvements with high performance should be considered (cf. [38]).

2.2.2 Integer Numbers.

We start this subsection with a comment of E. Borel (cf. [12]) : “... Il est intéressant d’essayer de classer les entiers qui peuvent être définis, d’après le temps nécessaire pour les définir, en admettant que l’on puisse, chaque seconde, prononcer un mot ou écrire un chiffre... Nous appellerons hauteur d’un nombre entier le temps minimum nécessaire pour le définir (exprimé en secondes, d’après les conventions précedéntes).”

Integers admit a similar discussion than that of polynomials. First, we have, of course, the binary encoding of integer numbers. The length of this encoding is what number theorists call the height of the number (cf. [8], [9],[15], [16], [77], [78], [79] for instance). Observe the difference with Borel’s approach, where hauteur is something closer to computing. On the other hand we encode numbers by straight–line programs. Such a encoding is simply an straight–line program that evaluates a polynomial without variables. Equivalently we can say that we evaluate an univariuate polynomial in the value 1 , i.e. we compile p(1) . Observe from Lemma 3, that the height of an integer evaluated by an straight–line program of size L and non–scalar depth ℓ is at most 2^{ℓ+1}log_{2}L. This depends exponentially on the depth and it is logarithmic on the size.

Last, but not least, the very limits of compression can be formulated in terms of Kolmogorov complexity : the Kolmogorov complexity of a number n ∈ IN is the smallest length of a word x ∈ {0, 1}^{∗} such that if x is the input of a Universal Turing machine, the binary encoding n is the output. In other words, it is the minimum length of programs whose output is the binary encoding of the number n ∈ IN . This definition clearly agrees with Borel’s ideas.

In order to compare the three approaches (binary, straight–line program and Kolmogorov complexity), let us consider the following examples :

C_{d} := \binom{2d}{d} E_{d} := 2^{2^{d}} − 1

The Catalan numbers C_{d} arise not only in elimination, but also as complexity estimates in Computational Geometry (cf.[50],[85]). These numbers require an O(log_{2}d) Kolmogorov complexity to be encoded, their height is of order O(d) and it is not known whether their size as straight–line programs is Ω(d) or not. The E_{d} numbers arise naturally in elimination and numerical analysis (cf. Section 3 below). Their height is exponential in d, 2^{d}, their straight–line program encoding needs O(d) space, and their Kolmogorov complexity is O(log_{2}d) .

Let us remark that for most integer numbers the three concepts agree up to a constant. In some sense, these examples belong to a very especial class of numbers.

2.3 Manipulating these Data Structures

The trade–off between compressing data and handling data is central to design procedures of low complexity. Of course, it is more difficult to manipulate compressed data than expanded ones. Compression is understood as saving all information about the data in smallest possible memory space. There is no interest in compressing up to the limits if we need again full expansion of the data in order to continue the procedure. Therefor we ha to specify how our compressed data are handled during our procedures. The following elementary operations are sufficient for modelling elimination methods :

• Arithmetic operations.

• Equality Tests.

We now overview the manipulation of straight–line program encodings of polynomials and integers. There are some other interesting problems with this type of data structure which we shall not discuss here. For instance, in [55], E. Kaltofen discussed algorithms for the factorization of multivariate polynomials given by straight–line programs. This data structure allows reduction to univariate case with few effort.

In the case of integer numbers there are several interesting open questions. The first one is related with the performance of algorithms in numerical analysis : is there a polynomial time algorithm that computes the sign of an integer from its straight–line program encoding?. Another interesting challenge is to obtain a polynomial time algorithm to factorize integers given by straight–line programs. In this sense, observe that Mersenne primes have small straight–line program encoding and polynomial time algorithms (cf. the Lucas and Lehmer primality tests in [83] or [54] and the references given there.

Floating Point Encoding. From the numerical analysis point of view a moment’s reflection is required. Some procedures for numerical solving are described in a continuous setting (over C for instance), i.e. as if the computer were able to handle any kind of complex numbers (cf. [11], [89] or [90]). Actually, numerical analysis software uses only rational numbers in floating point representation. This means that we aork with an encoding of rational numbers as pairs of integers, given in binary, where the denominator is a power of 10 . The numerical analysis approach adds a very special kind of operation : truncating the decimal expansion to preserve resource requirements. This implies, for instance, that one renounces to good approximations in order to preserve time and space bounds. The length of the truncated encoding of the output (the number of decimals used) yields a lower bound for the distance to authentic solutions.

2.3.1 Arithmetic operations.

Polynomials. Linear operations are easy for polynomials given in dense or sparse encoding. A little bit harder is multiplication. Best procedures are based on interpolation of polynomials given this way in order to compute the convolution.

For straight–line program encoding this execution of arithmetic operations is simpler. The input is is a pair of straight–line programs that represent two polynomials : f, g. The output is a straight–line program Γ that evaluates f ∗ g, where ∗ ∈ {+, −, ×}. An encoding of Γ is obtained by joining the two inputs and adding the new operation and the new gate. This means just to rewrite the new encodings of the gates. The case of Kolmogorov complexity is not more sophisticated. We have to consider just the particular features of Turing programs instead of arithmetic operations and directed acyclic graphs.

A clarifying example for this is substitution (this operation is very common in elimination).

Let us consider the polynomial Det(X_{ij}) , given as the determinant of an N ×N matrix with entries X_{ij}. Suppose that we have given n–variate polynomials F_{ij}(Y_{1}, …, Y_{n}) , of degree D. Let us encode the polynomial given by :

G(Y_{1}, …, Y_{n}) := Det(F_{i,j}(Y_{1}, …, Y_{n})) ∈ ZZ[Y_{1}, …, Y_{n}]

The dense representation of this polynomial has length \binom{ND+m}{m}. To write down this representation we have to evaluate G at \binom{ND+n}{n} well–chosen points. The procedure executes (ND)^{O(m)} arithmetic operations. In elimination, D and N are typically of order d^{n}. The whole procedure requires d^{O(n^{2})} arithmetic operations just to write down the output and this exponential bound is often met in elimination.

When straight–line program encoding is considered, the behaviour is different. Assume that the straight–line programs that evaluate the F_{i,j} ’s have size at most L. Thus the polynomial G can be encoded by an straight–line program Γ of size NL + N^{O(1)} and the procedure which generates Γ runs in polynomial time (NL)^{O(1)} . In terms of usual elimination estimates all this can be done in time d^{O(n)} .

Integers. As in the case of polynomials, arithmetic operations with integers given in binary representation are simple. However, operations such as exponentiation creates difficulties because of the output size.

• Exponentiation Given an integer x ∈ ZZ of height η and n ∈ IN , evaluate x^{2^{n}}.

Observe that this operation requires exponential time and space (2^{n}η)^{O(1)} if we use the data structure of binary encoding of integers .

In the straight–line program setting, arithmetic operations are as easy as those in the case of polynomials : we have only to paste the given straight–line programs and to add the new gates.

In the case of exponentiation straight–line program encoding provides much better estimates than binary expansion. Given x ∈ ZZ by a straight–line program of size L, the power x^{2^{n}} can be encoded by a straight–line program of size n + L. This can be done in linear time O(n + L) .

2.3.2 Equality tests.

Here, the question is to decide whether a given data is zero or not. If we are able to do that we can also decide whether two given data represent the same mathematical object. This task is straightforward in dense and sparse encoding. Unfortunately, in elimination procedures the degree grows exponentially and the decision of equality task becomes for this kind of encodings.

Equality tests seem to be harder in the straight–line program setting. We have no coefficients to compare and interpolation would increase the complexity. Since the nature of the straight–line programs comes from evaluation, the procedures to compare use evaluation as main instruction. The number of points where the evaluation is performed has to be small. It is possible to choose suitable points for this task at the price of witching to probabilistic procedures

Polynomials. There are two methods that deal with this problem. We call them the BPP and the P/poly approaches.

The BPP approach is given by a bounded error probabilistic polynomial time procedure in terms of the degree and the size of the straight–line program input. To stress the difference with the P/poly method, observe that the guessing in BPP procedures depends on the concrete input, whereas the P/poly method makes a guessing just depending on the input length. The BPP approach is considered in [86], [102], [53], [52].

The P/poly approach takes a fixed set of points of polynomial cardinality (questor sets or correct test sequences). This set of points depends just on the input length (the size of the straight–line program) and not on the concrete input. The algorithm evaluates the straight–line program at these points and gives always a correct answer if the questor set is correctly chosen. This approach can be seen for instance in [47], [27], [36], [58].

The difficulty here is that there is no known deterministic polynomial time algorithm that computes a questor set. Thus, there is an alternative probabilistic statement : guess a candidate to correct test sequence. This guessing is independent of the concrete input; it only depends on the input length. The error does not depend on the input but on the quality of the guess as questor. Some authors prefer to speak about non–uniform polynomial time algorithms with polynomial time advisors.

Thus, there is a probabilistic version where the guessing does not depend on the input. The guessing is done for fixed length and the error does not depend on the path followed by the input. It depends on the random choice of the questor set.

Integers. In this setting, equality test for integers given in binary is obvious. Instead of evaluating, the Chinese Remainder Theorem is used to do modular arithmetics with low error probability. As in the previous paragrapah, there are also two methods for the straight–line program encoding : BPP and P/poly. The BPP approach follows from the Lemma 2.5 in [51]. The P/poly approach has been recently obtained by J.L. Montaña and K. Hägele.

2.4 Parallelism

It is generally thought that parallelism is conceived just for design of parallel computers. This idea is almost true in some lines of research; but it has an important incidence here both for sequential time and space and, hence, in the design of sequential programs.

First of all, the results of A. Borodin show that parallel time is transformed in sequential space.

Theorem 4 ([13]) Given a sequence of LOG–space uniform boolean circuits of polynomial size and O(log_{2}^{i}n) depth, they can be simulated by a sequential Turing machine within space O(log_{2}^{i}n) .

In other words, depth (parallel time) is transformed in space. As many of the problems in computer algebra require enormous amounts of space, a control of the parallel time (depth) yields a control of the sequential space requirements. This yields a different programming philosophy with very few space resources for elimination problems. This is the main outcome in [67] and the implementations that are going on in the Universities of Buenos Aires and S. Luis (Argentina). (cf. also [30]).

Secondly, because of the bounds in [58], the increasing of intermediate integers (for instance, during the evaluation of polynomials and determinants) strongly depends on the non–scalar depth and not very much on the size (cf. Lemma 3 ). This is important for the Turing simulation of the procedure. For instance, a sequence of k operations of integers could provide a result of height 2^{k}. However, if these operations are described as a well–parallelizable straight–line program, the height will always be polynomial in k.

Third, parallelism seems to be closely related to the mathematical quantities. This can be seen, for instance, in the studies of lower bounds. In [60], it is observed that the degree of rational functions depends on the non–scalar depth. The topology and the geometry are related to the depth (parallel time) : degree, number of connected components ([71]), homology, Betti Numbers ([72]), the height of diophantine varieties ([59] and [58]).

Thus, studies of parallelism of algebraic procedures are essential not only because they could be modeled in a parallel computer architecture, but also because parallelism has a direct incidence in the sequential time and space of our procedures. Parallelism also contains a mathematical influence of the computer algebra procedures.

3 Lower Bounds

Usually lower bound statements are understood as lower bounds for a problem. This is not completely true. Lower bounds for a problem depend on the syntactical modelling of the problem. Their statements are usually obtained after a travel form syntax to semantics and back again. Every result on lower bounds must contain the following elements :

• A fixed syntactical modelling of the problem.

• An intrinsic property of the problem that yields some obstructions.

• A conclusion : “No improvement of a certain magnitude can be obtained while preserving this syntactical modelling”.

Thus, a lower bound has to be understood as an obstruction to the syntactical modelling of the problem.

First attempt to classify the complexity of a description of a problem consists on relating this problem with complexity classes. Main lower bounds statements below make use either of some hierarchy theorem or they bound the time by means of external memory requirements. This second method is useful to state lower bounds for division problems. Since we are discussing efficiency of modellings, we have to distinguish lower bounds from the several encodings above : Dense encoding, Sparse/Fewnomials encoding, Program encoding.

3.1 Dense Encoding of Inputs and Outputs

Polynomials are considered as words in 0 Q^{∗} = ∪_{n∈IN} 0 Q^{n}. The known lower bounds are based on estimations of the output length (i.e. external memory requirements). They mainly concern division problems. In this sense they are definitive : no polynomial time algorithm exists for this representation.

Theorem 5 ([69]) Given k, d ∈ IN, d ≥ 5, n := 10k,there are P_{1}, …, P_{n+1} polynomials in ZZ[X_{1}, …, X_{n}] such that deg(P_{i}) ≤ d, such that X_{1}−X_{n} is in the ideal (P_{1}, …, P_{n+1}) .

If X_{1} − X_{n} := ∑_{i=1}^{n+1} g_{i}P_{i}, then maxdeg(g_{i}) ≥ (d − 2)^{2^{k−1}}

The degree bound in this statement determines the length of an output polynomial in dense representation. This Theorem says that dense encoding of polynomials makes the division problem to be out of scope for any tractable complexity class. Similar order lower bounds with dense encoding of outputs can be found for the problem of quantifier elimination over algebraically (or real) closed fields of given characteristic in [25] or [28].

Let us now consider division problems for a more geometric class of ideals : the Division Problem in the Nullstellensatz. Several authors (D. Lazard, T. Mora, W. Masser, P. Philippon among others) have found the following example :

Proposition 6 Given the polynomial system f_{1} = X_{1}^{d}, f_{2} = X_{1}−X_{2}^{d}, …, f_{n−1} = X_{n−2}− X_{n−1}^{d}, f_{n} = 1 − X_{n−1}X_{n}^{d−1} ∈ 0 Q[X_{1}, …, X_{n}] , without common zeros in C^{n} .

If 1 := ∑_{i=1}^{n} g_{i}f_{i}, then deg(g_{1}) ≥ d^{n} − d^{n−1} .

Both results imply that dense encoding has arrived to its limits. The question is now how to avoid these encodings, how to represent polynomials in such a way that complexity becomes smaller.

3.2 Sparse Encoding of Inputs and Outputs

Here things do not seem to go better. For instance, E. Mayr used sparse encoding of inputs (cf. [68], [69]). He considers again the membership problem to arbitrary polynomial ideals. Thus, he was able to show the following theorem :

Theorem 7 ( [68]) The membership problem for polynomial ideals over 0 Q is a complete problem in the class EXPSPACE.

As an immediate consequence the time to solve it is at least exponential (and probably doubly exponential) and this lower bound cannot be improved because of the Time and Space Hierarchy Theorems (cf. [1]). Therefore, the general problem of ideal membership is placed out of the scope of any tractable (theoretical or practical) complexity class while sparse/fewnomials encoding is preserved.

It is also relevant the work of D.A. Plaisted in [80] who showed that the computation of the greatest common divisor of sparse univariate polynomials is NP- hard (cf. also [3]). However, one can easily observe that this encoding deserves exponential time even in the univariate case. It is enough to divide X^{2^{n}} − 1 by X − 1 . The input has O(n) length, while the sparse encoding of the output is exponential.

3.3 Program Encoding of Inputs and Outputs

While the previous lower bounds are definitive, the lower bounds based on program encoding of polynomials are only relative. This relativeness is caused because the lower bounds come from a reduction to a class in Structural Complexity, whose relation with tractable algorithms is not yet complete.

The first obvious statement is the following :

Proposition 8 If there is a Turing machine that solves the Weak Nullstellensatz in time polynomial in straight–line program input length, then P = NP.

This is because the input of 3SAT is given by straight–line programs of size O(n) .

Now, we concentrate our overview on the results of the work of J. Heintz and J. Morgenstern ([46]). First example concerns Elimination. These authors consider the 0− dimensional ideal generated by the polynomials

X_{1}^{2} − X_{1}, X_{2}^{2} − X_{2}, …, X_{n}^{2} − X_{n}

This defines a 0− dimensional affine variety of degree 2^{n}. The input polynomials can be evaluated by an straight–line program of size O(n) . The U− resultant is the polynomial that describes the set of linear forms u := u_{0} + u_{1}X_{1} + ⋯ + u_{n}X_{n} that vanish at some point of the variety. In other words, the minimal polynomial of u modulo the ideal (f_{1}, …, f_{n}) . Now one has :

Theorem 9 ([46]) If there is a polynomial time algorithm that outputs the U− resultant as straight–line program and this output verifies that, when evaluated the intermediate results do not grow very fast, then P = NP.

The reason is that the U− resultant is another formulation of the Knapsack Problem : which is NP-complete. Thus if a polynomial time algorithm is available, the output is a straight–line program of polynomial size. If this straight–line program can be evaluated with polynomial binary size intermediate results, we obtain a polynomial time algorithm for the Knapsack Poblem and P = NP.

A possible condition should be that the output were a polynomial size well–parallelizable straight–line program. In this case, the bounds for the height of the intermediate results would yield a polynomial time algorithm for the knapsack. However, using geometric invariants, in [71] it is shown that no straight–line program exists that solves the Knapsack and has depth smaller than \sqrt{n} (cf. also [101]).

The second lower bound in [46] is stated in the following terms. Sometimes the geometric problem has two distinguished sets of variables : some of them are free and some others are algebraically dependent. In other words, some of the variables occur as parameters. In this case we can distinguish between these two classes of variables. Thus, let us consider the field k := 0 Q(Z_{i,j} : 1 ≤ i, j ≤ n) and the ideal generated by the following polynomials :

X_{i,j}^{2} − X_{i,j}, for 1 ≤ i, j ≤ n

−1 + ∑_{i≤j≤n} X_{i,j}, for 1 ≤ j ≤ n

−1 + ∑_{1≤i≤n} X_{i,j}, for 1 ≤ j ≤ n

Y − ∏_{1≤i≤n}( ∑_{1≤j≤n} X_{i,j}Z_{i,j})

These polynomials are encoded by a straight–line program of size O(n^{2}) and define a variety V . We consider the image of this variety under the projection onto the Y coordinate. The image is an algebraic variety defined by a polynomial Q(Z_{i,j}, Y) ∈ 0 Q[Z_{i,j}, Y] . This polynomial has the following form :

D(Z_{i,j}, Y) := Y^{n!} − P (Z_{i,j})Y^{n!−1} + terms of lower degree

The polynomial P (Z_{i,j}) is the permanent. These authors show how to obtain the permanent from an straight–line program that evaluates Q(Z_{i,j}, Y) . Thus, they conclude :

Theorem 10 ([46]) If there is a polynomial time algorithm to solve elimination, such that the output is a monotone division free straight–line program, then the permanent n × n can be evaluated in sequential time n^{O(1)} .

And no method is known (and probably does not exists) that evaluates the permanent in a polynomial number of arithmetic operations.

The third lower bound shown in [46] is related to the Pochhammer–Wilkinson polynomial and the Catalan numbers. Recall that the Pochhammer polynomial is defined by :

P_{d}(T) := ∏_{i=1}^{d}(T − i)

In particular P_{d}(2d) = d!C_{d} (cf. Section 2). This polynomial arises quite naturally as an elimination problem. Consider again the ideal generated by :

X_{1}^{2} − X_{1}, X_{2}^{2} − X_{2}, …, X_{n}^{2} − X_{n}

Consider now the linear form :

Y := 1 + ∑_{i=1}^{n} 2^{i}X_{i}

Then, the image under the projection defined by Y is the subvariety of 0 Q given as the zero set of the Pochhammer polynomial P_{2^{n}}(Y) . It has an exponential number of zeros and the constant term has exponential binary size :

P_{2^{n}}(0) := 2^{n}! ≥ 2^{2^{n}}

If the encoding is sparse or dense, one concludes that elimination belong to the class EXTIME and that no improvement of complexity below exponential time exists.

It is not known whether P_{2^{n}}(T) requires an exponential size straight–line program to be evaluated. Some partial answers are :

Proposition 11 ([58]) If a straight–line program evaluates the Pochhammer polynomial P_{2^{n}}(Y) in size L and non–scalar depth ℓ, then

n2^{n} ≤ (2^{ℓ+1} − 1)log_{2}L

In particular, either L ≥ 2^{n} or the Catalan numbers can not be evaluated by a well– parallelizable straight–line program (i.e. its depth is of order Ω(n − log_{2}n) ).

Probabilistically there are very few non–well–parallelizable integer numbers.

It is still unknown whether the Pochammer polynomial requires a straight–line program of size 2^{n} to be evaluated. One may consider a real version for the same problem : quantifier elimination in first order language of real fields. One obtains :

Theorem 12 ([46]) Any straight–line program encoding of the polynomial that describes the projection onto the variable Y of the semi–algebraic set given by the formula :

X_{1}^{2} − X_{1} = 0, …, X_{n}^{2} − X_{n} = 0, Y^{2} − (1 + ∑_{i=1}^{n} 2^{i}X_{i}), Y > 0

has size of order \frac{2^{n}}{n} .

It could be said that there is no surprise in this phenomenon. The real algebraic framework contains the sign condition > which is not reflected by the straight–line program setting. It seems as if straight–line programs were more accurate for the complex case than for the real one.

3.4 Numerical Analysis

We observe that numerical analysis has similar obstructions as those in computer algebra. They may be explained in terms of encoding of integers. Let us consider the following example :

X_{1} − 2 = 0, X_{2} − X_{1}^{2} = 0, …, X_{n} − X_{n−1}^{2} = 0  (4)

This example is a diophantine version of the of Mora, Lazard, Masser and Philippon example mentioned above. The idea behind is that height corresponds to degree, in the case of integers (cf. [58], [15], [79]). Thus, we have

Proposition 13 With binary encoding of integers, multivariate numerical solving is in EXTIME and requires an exponential amount of space (i.e. EXPSPACE). Thus it is a strongly intractable problem.

This is another proof of the obvious P_{w} ≠ NP_{w} inequality in Koiran’s weak model (cf. also [24]). The idea is simply that any rational point a ∈ 0 Q^{n}, close to the unique solution of the system above has exponential height. In other words, multivariate numerical solving has to include alternative data structures for integers in order to be efficient (cf. also [91]).

This is not only a feature of multivariate numerical solving. Even the univariate case has some obstructions too. For instance, let us recall the Liouville theorem :

Theorem 14 Let α ∈ C be an algebraic complex number, f ∈ ZZ[X] its minimal polynomial, d a bound of the degree of f , and let h be an upper bound of the height of the coefficients of f . Then, there is a constant, depending only on α, c(α) , such that for every a := \frac{c+d.i}{q} ∈ 0 Q[i] , a, d, q ∈ ZZ , q > 0 ,the following inequality holds :

\frac{c(α)}{q^{d}} <|| α − a ||

The constant c(α) can be estimated by :

((d + 1)(2^{h} + 1))^{−(d+2)} ≤ c(α)

These bounds stated, we can obtain by simple comparison of the two inequalities the following :

Corollary 15 Newton’s method, with binary encoding (or floating point encodings) of integers and rationals, univariate numerical analysis could never obtain approximations a ∈ 0 Q[i] such that :

|| α − a ||< ε = \frac{1}{2^{2^{dh}}}

in less than EXTIME.

This lower bound could be improved if one would be able to bound the constant of the Thue-Siegel-Roth theorem.

This phenomenon is a side efect of the binary encoding of rational (integer) numbers and not of the quadratic convergence of Newton’s method. Nevertheless, let us observe that Newton’s method produces a extremely efficient straight–line program containing divisions. The number of Newton iterations is the parallel time of the procedure. In other words, using straight–line program encoding of integer numbers, one obtains a number a ∈ 0 Q[i] such that

|| α − a ||< ε = \frac{1}{2^{2^{dh}}}

in time (dh)^{O(1)} . Due to this representation the output is apparently difficult to handle, but it respects the given limits of accuracy.

3.5 Final Comments

The previous lower bounds give a clear description of the problems of elimination in terms of structural complexity classes. Recall that we consider the class of polynomial time procedures P as the class of tractable problems. Thus, the membership problem for arbitrary ideals is extremely far from P independently of the encoding of the input. It is clear that only division modulo an ideal with geometrical meaning can be expected to be tractable. Examples of ideals with geometrical meaning appear in the Division Problem modulo either the trivial ideal (Nullstellensatz) or complete intersection ideals (including the 0− dimensional case).

In case ofr the Nullstellensatz we have considered the different approaches. If the input is given in dense encoding and if d ≥ n, the input length is estimated as N := d^{n}. The example of Mora–Lazard–Masser–Philippon puts this problem (under dense encoding of the output) into the class EXTIME and no improvement is possible. In the case d << n, d = 2 for instance, the same example shiows that the time to write the dense encoding of the output cannot be done in less than 2^{n^{2}} time, where n is the input length meausred in sparse encoding. In other words, this encoding of polynomials puts our problems within the classes of strongly intractable complexity and this lower bound is definitive :

EXTIME ⟶ NEXTIME ⟶ DEXTIME

↘

EXPSPACE

In the case d ≥ n, dense encoding of inputs and straight–line program encoding of outputs admits polynomial time procedures. This will be discussed in the following Section.

As in the case of dense encoded input polynomials lower complexity bounds are just relative if the input is given in straight–line program encoding. The most one can say is that the lower complexity bounds depend on the open conjecture P ≠ NP . Moreover, these estimates will reflect the natural estimates of computer science. In other words, this approach still constitutes an open door for improvements and some promising results are given in [38].

The second conlusion is that numerical analysis has similar obstructions as computer algebra. Binary encoding of integers drives multivariate numerical solving into the class EXTIME, while it can be expected that straight–line program encoding of integers provides good approximations in polynomial time.

4 Upper Bounds

In this section we concentrate our exposition on upper bounds for the Nullstellensatz and the Division Problems. To state these upper bounds we distinguish the different encodings of inputs and outputs that were previously stated. The estimates are described in terms of the input length.

• Dense encoding of inputs and outputs.

• Sparse encoding of inputs and outputs.

• Dense encoding of inputs and straight–line program encoding of outputs and intermediate results.

• Program encoding of inputs and outputs.

Because of the space limitations, we do not discuss the sparse/fewnomials approach. We refer the reader to [99] and the references given there.

4.1 Dense Encoding of Inputs and Outputs

There are two main approaches dealing with this data structure. One of them, the Gröbner basis approach, is discussed in the surveys [19],[62], [73]. The second approach is based on degree estimates of the output polynomials and has shown to be the most efficient.

As above, we assume that there is given an input system of polynomials f_{1}, …, f_{s} in n variables, with integer coefficients of degree at most d ≥ n, and of height at most h. Thus, the input length (in dense encoding) can be estimated by d^{n}sh. The question is whether there are a ∈ ZZ , a ≠ 0 and polynomials g_{1}, …, g_{s} ∈ ZZ[X_{1}, …, X_{n}] such that the following equation holds :

a = g_{1}f_{1} + ⋯ + g_{s}f_{s}  (5)

In case of an affirmative answer, the constant a ∈ ZZ and the polynomials g_{1}, …, g_{s} are also required.

A first bound for the degree of the g_{i} ’s was obtained in 1926 as a consequence of the work of G.Hermann ([49]). Later on, D.W.Masser and G.Wüsholz ([65]) extended transcendence proofs of A.Gel’fond ([33] and [87]). Using the methods of [49], they obtained upper bounds for the height of a and the coefficients of the polynomials g_{1}, …, g_{s}. Both results lead to bounds of order d^{2^{n}} for the degrees and d^{2^{n}}h for the binary size of a and for the coefficients of the g_{i} ’s, which is far from being tractable.

The bounds for the degrees of the polynomials g_{1}, …, g_{s} were successively improved in [17], [20] and [57] (or more recently in [84]) to deg f_{i}g_{i} ≤ max{3, d}^{n}.

These estimates reduce the Effective Nullstellensatz to the resolution of a linear system of equations. We are thus working into a linear algebra setting. Inputs are vectors (monomial coefficients), outputs are vectors, intermediate operations are matrix operations. At this point well-parallelizable algorithms for matrix computations ([7], [74]) provide a method to improve space bounds. This is the idea in [21]. The linear system contains as many variables as monomials of degree at most max{3, d}^{n} (whereas a is simply the determinant of a maximal minor of the system matrix). This leads to a number of coefficients in dense encoding of order ( sd^{n^{2}} ) of binary size d^{O(n^{2})} log_{2} η^{O(1)} . As observed in [21], by transforming Berkowitz algorithm for the determinant in boolean circuits and transforming the parallel time in sequential space (cf. [13]), this gives poly–logarithmic bounds (n log_{2} d)^{O(1)} for the working space (cf. also [67]. Nevertheless, this procedure still requires an exponential amount of “external memory” ( d^{O(n^{2})} ). This yields an exponential lower bound ( d^{Ω(n^{2})} ) for the sequential time with respect to the input size. In particular, the procedure will be in EXTIME for dense encoding of inputs.

In [8] and [9], C.Berenstein and A.Yger obtained a division theorem in terms of complex integrals which implies the following more accurate bound for the heights in identity (5) :

max{ height(a), height(g_{i})} ≤ κ(n)d^{8n+3}(h + d log_{2} d)

(where κ(n) is an effective constant depending only on n).

As we have seen in Section 3, the d^{n} bounds for degree and height are optimal. These lower bounds suggest the look for another way in order to improve efficiency. No advance in terms of complexity can be expected while maintaining the underlying dense encoding of polynomials.

4.2 Dense Encoding of Inputs and Program Encoding of Outputs

The alternative consists in avoiding big amount of external memory. This is the main line of the algorithms given in a series of papers ([35] [36], [37], [27], [58]) and this is the way we are going to describe. The improvement uses straight–line program encoding of polynomials. As we have said in Section 2, the original idea comes from the eighties, when univariate elimination problems were considered. However, in the univariate case, one cannot see the efficiency of this encoding. It is the case of multivariate elimination where this encoding reaches significant efficiency. The discovery is that in spite of the potentially high degree of polynomials occurring in elimination, they have short descriptions by straight–line programs. The rest of the section is devoted to sketch these results :

Straight–line program for multivariate algebraic geometry problems appear implicitly in the work of M. Giusti and J. Heintz [35]. Variables play a different role depending on the step of the procedure. At every step, some of them arise as parameters and some others as dependent variables which have to be eliminated. In the parameter case variables are treated almost as constants. This yields a mixed encoding of polynomials. This philosophy provides a first important improvement for the computation of the dimension of affine varieties and, in particular, the computation of Noether normalization, and the description of the isolated points of the given variety (or ideal) :

Theorem 16 ([36])“Une variété algébrique étant donnée par équations, le calcul de la dimension, sa mise en position de Noether et la détermination de ses points isolés peuvent se faire en temps polynomial par rapport á l’entrée, et ce de manière non–uniforme”.

It must be said the the adjective “polynomial” means that the algorithm performs s^{O(1)}d^{O(n)} arithmetic operations.

The straight–line program encoding of outputs for the Division Problem was first considered in [37]. The main outcome is the following :

Theorem 17 ([37]) Let k be a perfect infinite field, f_{1}, …, f_{s} ∈ k[X_{1}, …, X_{n}] polynomials of degree at most d ≥ n. In s^{O(1)}d^{O(n)} arithmetic operations we can decide whether the constant 1 belongs to the ideal generated by f_{1}, …, f_{s}) . In case of affirmative answer, we can compute polynomials p_{1}, …, p_{s} of degree d^{O(n^{2})} , encoded by a well–parallelizable straight–line program (with divisions), of size s^{O(1)}d^{O(n)} such that :

1 = p_{1}f_{1} + ⋯ + p_{s}f_{s}

Observe that this procedure outputs straight–line program whose underlying graph has polynomial size d^{O(n)} , but there is no estimate of the integers arising during this computation. However, this bound is not optimal because of the d^{O(n^{2})} degree bounds and the presence of divisions in the output straight–line program. Moreover, the complexity estimates make reference just to the number of arithmetic operations (size), while the depth is about O(n^{2} log_{2}^{2} d) . In terms of Turing machine complexity, this procedure risks to be still exponential, because of the depth : recall that the height of the integers depends exponentially on the depth, i.e. these bounds could mean that we are manipulating numbers of height d^{O(n^{2})} .

To improve the degrees of the output, in [27] the authors observed that duality in Gorenstein algebras can be combinaed in a very natural way with straight–line program encoding of polynomials. After [27] duality became of common use in computer algebra; but it was applied to different purposes in [5], [22]. We have now :

Theorem 18 (cf. [27]) With the notations of Theorem 17, there exists an arithmetic network over k of size s^{O(1)}d^{O(n)} and depth O(n^{2}log_{2}^{2}sd) which dedices whether the ideal (f_{1}, …, f_{s}) is trivial. If this is the case the network constructs a division–free straight– line program β which represents polynomials p_{1}, …, p_{s} ∈ k[X_{1}, …, X_{n}] such that the following conditions are fulfilled :

• the size of β is s^{O(1)}d^{O(n)} and its depth is O(n^{2}log_{2}^{2}sd) .

• the polynomials are of degree d^{O(n)} and satisfy 1 = p_{1}f_{1} + ⋯ p_{s}f_{s}.

There iss still a problem to solve. It concerns the depth of the algorithm which is still of order O(n^{2}log_{2}^{2}d) . This implies that the procedure risks to be exponential because of the growing heights of intermediate results. It is also necessary to specify the Turing complexity of the procedure. In [58], the authors answered this question. The new outcome was a control of the non–scalar depth (of order O(n log_{2} d) ) of the straight–line programs which arise both in the Nullstellensatz and the Membership Problem in complete intersection ideals. thus, we have the following result :

Theorem 19 ([58]) Let f_{1}, …, f_{s} be polynomials in ZZ[X_{1}, …, X_{n}] of degree and height bounded by d ≥ n and h respectively, which don’t share any zero in C^{n}.

Then there exist a straight–line program of size sd^{O(n)} , non–scalar depth O(n log_{2} d) and integer parameters of height max{O(n log_{2}d), h} which evaluates an integer number a ∈ ZZ − {0} and polynomials g_{1}, …, g_{s} ∈ ZZ[X_{1}, …, X_{n}] such that :

a = g_{1}f_{1} + ⋯ + g_{s}f_{s}.

In fact not only the external memory requirement is low, even the procedure runs in polynomial time too :

Corollary 20 ([58]) The Effective Nullstellensatz and the Membership Problem to Complete Intersection Ideals can be solved by a Turing machine that runs within BPP(i.e. bounded error probabilistic polynomial time) for dense encoding of inputs.

This theorem has also consequences of a more mathematical nature : the optimal bounds for the degree and the height of the polynomials in the Nullstellensatz arise quite naturally as consequence of the complexity estimates for straight–line programs :

Corollary 21 ([58]) Let f_{1}, …, f_{s} be polynomials in ZZ[X_{1}, …, X_{n}] of degree and height bounded by d ≥ n and h respectively, which don’t share any zero in C^{n}. Then, there exist an integer a ∈ ZZ − {0} and polynomials g_{1}, …, g_{s} that are also in the ring ZZ[X_{1}, …, X_{n}] such that :

• deg g_{i} = d^{O(n)} (1 ≤ i ≤ s)

• max{height(a), height(g_{1}), …, height(g_{s})} = d^{O(n)} max{h, log_{2} s}

Moreover, these polynomials are the outputs of the algorithm in Corollary 20

4.3 Program Encoding of Inputs and Outputs

In the introduction we observed that most computer science problems can also be formulated as computer algebra problems. The idea was that we can translate a problem formulated in terms of computer science objects into a polynomial system. This translation is particularly simple when the original computer science problem is formulated in terms of propositional calculus. However, once the translation is made, the usual estimates of input length in dense/sparse encoding of polynomials do not reflect the original input length of the computer science formulation of our procedure. For instance, the formula :

(¬X_{1}) ∧ (¬X_{2}) ∧ ⋯ ∧ (¬X_{n})

has a computer science input length of order O(n) . The polynomial corresponding to this formula is usually given as :

(1 + X_{1})(1 + X_{2}) ⋯ (1 + X_{n})

This polynomial has dense/sparse encoding of length at least exponential in the computer science input length 2^{n}. Even the polynomial time procedures of Subsection 4.2 above would run in time 2^{O(n)} for any input system containing this polynomial. In other words, the procedures would behave on real computers as if they were exponential time (and hence intractable) just because the dense encoding of inputs does not reflect the particular feature of the input system.

A surprising example is the following one : consider the system of polynomial equations given by

X_{1} − X_{1}^{2} = 0, …, X_{n} − X_{n}^{2} = 0, −512 + 2X_{1} + ⋯ + 2^{n}X_{n} = 0

This input system has a solution if and only if n ≥ 9 and the solution is the binary expansion of 512. Solving this polynomial system is something that computers can make easily if they know they are computing the binary expansion of 512, but computer algebra procedures to solve it require exponential time. The reason is that the input system has degree at most 2 in n variables and best procedures above would require time 2^{O(n)} . This is reflected by the experimentation with most commonly used computer algebra packages that require enormous amounts of time and space simply to detect that 512 = 2^{9} holds. This effect is not due to a bad polynomial encoding of the problem. The effect is due to the fact that dense encoding of inputs and outputs hides the particular feature of a problem like this. The computer science encoding of our problem is simple whereas its dense polynomial fashion encoding is enormous.

Thus, an investigation of the behaviour of computer algebra procedures has to take into account complexity estimates in terms of input length from a more computer science point of view. For input polynomial systems obatined as a translation of a computer science problem, the computer algebra input length must be defined in such a way that it reflects the computer science aspect. A possibility consists in considering the complexity of procedures when the input is encoded by straight–line programs. Thus, the size of the straight–line program that encodes the input system L is the parameter for complexity estimates.

Some commonly used computer algebra procedure are now discarded. For instance, to write down the coefficients of the input system recovering thus the dense encoding of the input polynomials, requires time complexity of order d^{n}. This reduces to general procedures as those in described previous subsections and in this way we shall never be able to discard and apply the special feature of our input system.

A way to avoid this obstruction is in [38]. This paper deals with the first step in the studies of all contained problems above : the problem of Elimination (cf. Section 2 above). The problem consist on describing the image of a 0− dimensional affine algebraic variety under a linear mapping. This means is solving of polynomial equation systemsin the computer algebra setting.

Most commonly used methods for elimination reduce this problem from the affine to the projective case. Since this cannot be done directly, an homotopic deformation is needed. The kown complexity estimates for elimination in projective spaces rely on dense encoding of polynomials (cf. [61]) and depends on the regularity of the Hilbert function. Thus, if d is a bound for the degrees of the polynomial inputs and n is the number of variables involved, usual procedures have time complexity polynomial in :

\binom{nd}{n}

The outcome are again complexity estimates of order d^{O(n)} and we recover the estimates of Subsection 4.2 above.

A procedure aiming to obtain polynomial time complexity estimates in terms of straight– line programs size has to avoid reductions to the projective case and dense representation of intermediate results. This is the attempt developped in [38]. We assume now that our input is a regular sequence f_{1}, …, f_{n} ∈ 0 Q[X_{1}, …, X_{n}] of polynomials of degree at most d, given by a straight–line program β of size L. We define δ as the maximum of the (affine) degrees of the algebraic varieties :

{x ∈ C^{n} : f_{1}(x) = ⋯ = f_{i}(x) = 0}

We this assumtptions and notations we have the following result :

Theorem 22 ([38]) Assume that f_{1}, …, f_{n} form a regular sequence in 0 Q[X_{1}, …, X_{n}] . Then, there exists an arithmetic network with FOR gates which, from the input given by β and a linear form H, computes the coefficients of a non–zero polynomial p ∈ k[T] such that p(H) vanishes on V = V (f_{1}, …, f_{n}) .The nonscalar size and depth of the network are (ndδL)^{O(1)} and O(n(log_{2}(δd) + ℓ)) respectively.

The method requires especific procedures of elimination for polynomials given by straight–line programs. In some sense this is a first step to transform computer algebra procedures in something closer to computer science procedures. But this is simply a first view on a large field. I refer the interested reader to the paper [38] in this volume for more details.

4.4 Final comments

Investigation of theoretical complexity aims to explain the behaviour of real computers when running a procedure. Thus practical computing and implementation of computer algebra procedures must reflect some of the conclusions above in order to improve the efficiency of its procedures when dealing with geometrical problems. It is now clear that commutative algebra problems include intractable problems as the Membership problem for arbitrary ideals. It is also clear than only geometric problems are of interest for practical computing because they do not necessarily overload real computers. However, simple data structures as dense encoding of outputs may put problems (as the Division in the Nullstellensatz) into strongly intractable complexity classes.

On the other hand, it is now clear that for dense encoding of inputs, and d ≥ n, straight–line program encoding of outputs allows polynomial time procedures and puts this kind of problems among those classified as tractable and with interest in practical computing (i.e. the low classes in our diagram of Section 2)

P ↘

BPP ⟶ NP ⟶ PSPACE

Finally, it must be clear that avoiding ill–posed algebraic versions of computer science problems requires a reflection on the data structure both for the input, the output and the intermediate results. A possible way out consists in estimating complexity in terms of the straight–line program encoding of inputs and not only in terms of the dense encoding of inputs.

Acknowledegements.

I gratefully acknowledge the splendid help of J. Heintz when writing these pages. I also sincerely thank the comments and suggestions of T. Recio and M. Giusti. Finally, I would also like to thank the organizers of the AAECC–11 conference for their kind invitation to give this talk.

5 References

The bibliography that follows is not intended to be exhaustive. Interested readers may found additional references in any of the quoted papers.

References

[1] J.L. Balcazar, J.L. Díaz and J. Gabarró. “Structural Complexity I”. EATCS Mon. on Theor. Comp. Sci. 11, Springer (1988).

[2] W. Baur, V. Strassen. “The complexity of partial derivatives”. Theoret. Comput. Sci. 22 (1982) 317–330.

[3] D. Bayer. “The Division Algorithm and the Hilbert Scheme”. Ph. D. Thesis. Harvard University (1982)

[4] D. Bayer, D. Mumford. “What can be computed in algebraic geometry?”. In Computational Algebraic Geometry and Commutative Algebra”, Proc. of the Cortona Conf. on Comp. Algebraic Geometry and Commutative Algebra, D. Eisenbud and L. Robbiano (eds.). Symposia Matematica, vol. XXXIV, Istituto Nazionale di Alta Matematica, Cambridge University Press (1993) 1–49.

[5] E. Becker, J.P. Cardinal, M.F. Roy, Z. Szafraniec. “Multivariate Bezoutians, Kronecker symbol and Eisenbud–Levine formula”. To appear in Proc. MEGA’94, Brikhaüsser Progress in Math.

[6] M. Ben–Or. “Lower Bounds for Algebraic Computation Trees.” In ACM 15^{th} Symposium on Theory of Computation, (1983) 80–86.

[7] S.J. Berkowitz.“On computing the determinant in small parallel time using a small number of processors”, Inf. Proc. Letters 18 ( 1984) 147–150.

[8] C. Berenstein and A. Yger. “Effective Bézout identities in 0 Q[X_{1}, …, X_{n}] ”, Acta Math., 166 ( 1991 ) 69–120.

[9] C. Berenstein and A. Yger. “Une Formule de Jacobi et ses conséquences”, Ann. Sci. E.N.S., 4^{ieme} série, 24 ( 1991 ) 363–377.

[10] L. J. Billera, I. M. Gel’fand and B. Sturmfels. “Duality and Minors of Secondary Polyhedra.” J. Combinatorial Theory, Vol. 57, No. 2 (1993) 258–268.

[11] 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”. Bulletin of the Amer. Math. Soc., vol.21, n. 1, (1989) 1–46.

[12] E. Borel. “La définition en mathématiques”. In Les Grands Courants de la Pensée Mathématique, Cahiers du Sud, Paris, (1948), 24–34.

[13] A. Borodin. “On Relating Time and Space to Size and Depth”. SIAM J. on Comp. 6 (1977) 733-744.

[14] A. Borodin, J. Munro.“The Computational Complexity of Algebraic and Numeric Problems”. Elsevier, NY, (1972).

[15] J.-B. Bost, H. Gillet and C. Soulé. “Un analogue arithmétique du théorème de Bézout”, C.R. Acad. Sci. Paris, t. 312, Série I ( 1991 ) 845–848.

[16] J.-B. Bost, H. Gillet and C. Soulé. “Heights of projective varieties and positive Green forms”, Manuscrit I.H.E.S. ( 1993 ).

[17] D. W. Brownawell. “Bounds for the degree in the Nullstellensatz”, Annals of Math. 126 ( 1987 ) 577–591.

[18] D.W. Brownawell. “Local Diophantine Nullstellen inequalities”, J. Amer. Math. Soc. 1 ( 1988 ) 311–322.

[19] B. Buchberger. “Gröbner bases: An algorithmic method in polynomial ideal theory”. In Multidimensional System Theory (N.K. Bose, ed.), Reidel, Dordrecht (1985) 374-383.

[20] L. Caniglia, A. Galligo and J. Heintz. “Borne simplement exponentielle pour les degrés dans le théorème des zéros sur un corps de caractéristique quelconque”, C.R. Acad. Sci. Paris, t. 307

Série I ( 1988 ) 255–258.

[21] L. Caniglia, A. Galligo and J. Heintz.“Some new effectivity bounds in computational geometry”. In Proc. AAECC-6, (T. Mora. ed.), Springer LNCS 357 (1989) 131-151.

[22] J.P. Cardinal.“Dualité et algorithmes itératives pour la solution des systémes polynomiaux”. Thése, U. de Rennes I (1993).

[23] F. Cucker, J.L. Montaña, L.M. Pardo.“Time Bounded Computations over the reals”. Int. J. of Alg. and Comp., Vol.2, No. 4 , (1992) 395–408.

[24] F. Cucker, M. Shub, S. Smale. “Separation of complexity lasses in Koiran’s weak model”. Theor. Comp. Sci. 133, N. 1, (1994) 3–15.

[25] J. Davenport, J. Heintz. “Real quantifier elimination is doubly exponential”. J. Symbolic Computation 5 (1988) 29–35. Reprinted in: Algorithms in Real Algebraic Geometry, ed. by Denis A. Arnon and Bruno Buchberger, Academic Press (1988) 29–35.

[26] D. Duval.“Diverses Questions Relatives au Cacul Formel avec des Nombres Algèbriques”. Thèse d’ Etat, Grenoble (1987).

[27] N. Fitchas, M. Giusti and F. Smietanski. “Sur la complexité du théorème des zéros”, Manuscript

Ecole Polytechnique ( 1993 ).

[28] N. Fitchas, A. Galligo, J. Morgenstern. “Algorithmes rapides en séquentiel et en parallele pour l’élimination de quantificateurs en géométrie élémentaire”. Seminaire de Structures Algebriques Ordennes, Université de Paris VII (1987).

[29] M. Garey, D. Johnson.“Computers and Intractability : A Guide to the Theory of NP–completeness”. Freeman, San Francisco (1979).

[30] J. von zur Gathen. “ Parallel algorithms for algebraic problems”. SIAM J. Comput., Vol. 13, No. 4 (1984) 802–824

[31] J.Von zur Gathen.“Parallel arithmetic computations: a survey”. In Proc. 13^{th} Mathematical Foundations on computer Science, ,(1986) 93–112.

[32] J. von zur Gathen. “Algebraic Complexity Theory”. Annual Review of Computer Science, vol. 3 (1988).

[33] A.O. Gel’fond. “Transcendental and Algebraic Numbers”. Dover,NY ( 1960 ).

[34] P. Gianni, T. Mora. “Algebraic solution of systems of polynomial equations using Gröbner bases”. In Proc. AAECC–5, LNCS 356 (1989) 247–257.

[35] M. Giusti and J. Heintz. “ Algorithmes –disons rapides– pour la décomposition d’une variété algébrique en composantes irréductibles et équidimensionelles”, In Proc. MEGA’90, Birkhäuser Progress in Math. 94, (T. Mora and C. Traverso, eds.) ( 1991 ) 169–193.

[36] M.Giusti and J.Heintz. “La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial”. In Computational Algebraic Geometry and Commutative Algebra”, Proc. of the Cortona Conf. on Comp. Algebraic Geometry and Commutative Algebra, D. Eisenbud and L. Robbiano (eds.). Symposia Matematica, vol. XXXIV, Istituto Nazionale di Alta Matematica, Cambridge University Press (1993) 216–256.

[37] M. Giusti, J. Heintz and J. Sabia. “On the efficiency of effective Nullstellensätze”. Computational Complexity 3 ( 1993 ) 56–95.

[38] M. Giusti, J. Heintz, J.E. Morais, L.M. Pardo. “When polynomial equation systems can be solved ’ fast’ ?”. In this volume (1995).

[39] L. Gonzalez Vega. “Determinantal formulae for the solution set of zero– dimensional ideals”. J. of Pure and App. Algebra, 76 (1991) 57–80.

[40] D. Yu. Grigor’ev. “Lower Bounds in Algebraic Computational Complexity”. J. of Soviet Mathematics, 4 (1988) 65–108.

[41] P. Gritzmann and B. Sturmfels. “Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases.” SIAM J. Disc. Math., Vol. 6, No. 2 (1993) 246–269.

[42] J. Heintz. “Definability and fast quantifier elimination over algebraically closed fields”. Theor. Comp. Science 24, (1983) 239–278.

[43] J. Heintz. “On the computational complexity of polynomials and bilinear mappings”, Proc. AAECC-5, Springer LNCS 356 ( 1989 ) 269-300.

[44] J. Heintz, T. Recio and M.F. Roy. “Algorithms in Real Algebraic Geometry and Applications to Computational Geometry”. DIMACS series in Discrete Math. and Theor. Comp. Sci. 6 (1991) 137–162.

[45] J. Heintz, M.-F. Roy and P. Solerno. “Sur la Complexité du Principe de Tarski-Seidenberg”. Bull. Soc. Math. de France 118, (1990) 101–126.

[46] J. Heintz and J. Morgenstern. “On the intrinsic complexity of elimination theory”. J. of Complexity 9 ( 1993 ) 471–498.

[47] J. Heintz and C.P. Schnorr. “Testing Polynomials wich are easy to compute”. In Logic and Algorithmic (an International Symposium in honour of Ernst Specker), Monographie n. 30 de l’Enseignement Mathématique (1982) 237–254. A preliminary version appeared in Proc. 12th Ann. ACM Symp. on Computing (1980) 262–268.

[48] J. Heintz and M. Sieveking. “Lower Bounds for polynomials with algebraic coefficients”, Theoret. Comp. Sci. 11 (1980) 321–330.

[49] G. Hermann.“Die Frage der endlich vielen Schritte in der Theorie der Polynomideale”. Math. Ann. 95 ( 1926 ) 736–788.

[50] F. Hurtado and M. Noy. “Ears of triangulations and Catalan numbers”. To appear in Discrete Mathematics.

[51] O.H. Ibarra, S. Moran. “Equivalence of Straight–Line Programs”. J. of the ACM 30 (1983) 217–228.

[52] O.H. Ibarra, S. Moran, E. Rosier. “Probabilistic algorithms and straight–line programs for some rank decision problems”. Inf. Proc. Letters, Vol. 12, No. 5 (1981) 227–232.

[53] E. Kaltofen. “Greatest common divisors of polynomials given by straight–line programs”. J. of the ACM, 35 No. 1 (1988) 234–264.

[54] D.E. Knuth. “The Art of Programming (vol. 2) : Semi–numerical Algorithms” Addison–Wesley (1981).

[55] E. Kaltofen. “Factorization of Polynomials given by straight–line programs”. In Randomness in Computation, Advances in Computing Research 5 (1989) 375–412

[56] H. Kobayashi, T. Fujise and A. Furukawa. “Solving systems of algebraic equations equations by general elimination method”. J. Symb. Comp. 5 (1988) 303–320.

[57] J. Kollár. “Sharp Effective Nullstllensatz”, J. of AMS. 1 ( 1988 ) 963–975.

[58] T. Krick, Luis M. Pardo. “Une approche informatique pour l’approximation diophantienne”. Comptes Rendues de l’Acad. des Sci. Paris, t. 318, Série I, no. 5 , ( 1994 ) 407–412.

[59] T. Krick, L.M. Pardo. “A Computational Method for Diophantine Approximation”. To appear in Proc. MEGA’94, Birkhäusser Verlag, (1995).

[60] H.T. Kung. “New algorithms and lower bounds for the parallel evaluation of certain rational expressions and recurrences”. J. of the ACM, 23, (1976) 534–543.

[61] D. Lazard. “Résolution des systèmes d’équations algébriques”, Theor. Comp. Sci. 15 ( 1981 ) 77– 110.

[62] D. Lazard. “ Systems of Algebraic Equations ( Algorithms and Complexity)”. In Computational Algebraic Geometry and Commutative Algebra”, Proc. of the Cortona Conf. on Comp. Algebraic Geometry and Commutative Algebra, D. Eisenbud and L. Robbiano (eds.). Symposia Matematica, vol. XXXIV, Istituto Nazionale di Alta Matematica, Cambridge University Press (1993) 216–256.

[63] A.K. Lenstra, H.W. Lenstra. “Algorithms in Number Theory”. In Handbook of Theoretical Computer Science, Elsevier, ch. 12 ( 1990 ) 673–715.

[64] M. Li and P.M.B. Vitányi. “Kolmogorov Complexity and its Applications”. In Handbook of Theoretical Computer Science, Elsevier, ch. 4 (1990) 187–254.

[65] D. W. Masser and G. Wüstholz. “Fields of large transcendence degree generated by values of elliptic functions”, Invent. Math. 72 ( 1971 ) 407–463.

[66] G. Matera. “Integration of multivariate rationals functions given by straight–line programs”. In this volume (1995).

[67] G. Matera, J.M. Turull. “The complexity of elimination : upper bounds”. Work in preparation (1995).

[68] E. Mayr. “Membership in Polynomial Ideals over 0 Q Is Exponential Space Complete”.

[69] E. Mayr and A. Meyer. “The complexity of the word problem for commutative semigroups ”, Advances in Math. 46 ( 1982 ) 305–329.

[70] M. Mignotte. “Mathématiques pour le Cacul Formel”, Presses Univ. de France ( 1989 ).

[71] J.L.Montaña and L.M.Pardo.“Lower bounds for Arithmetic Networks”. AAECC 4 (1993) 1–24.

[72] J.L. Montaña, J.E. Morais, L.M. Pardo. “Lower Bounds for Arithmetic Networks II :Sum of Betti Numbers”.To appear in AAECC 7 (1995).

[73] T. Mora, L. Robbiano. “Points in Affine and Projective Sapces”. In Computational Algebraic Geometry and Commutative Algebra”, Proc. of the Cortona Conf. on Comp. Algebraic Geometry and Commutative Algebra, D. Eisenbud and L. Robbiano (eds.). Symposia Matematica, vol. XXXIV, Istituto Nazionale di Alta Matematica, Cambridge University Press (1993) 216–256.

[74] K. Mulmuley. “A fast parallel algorithmn to compute the rank of a matrix over an arbitrary field”. COMBINATORICA, 7( 1 ) (1987) 101–104.

[75] Newton,I. “De Analysi per Aequationes Infinitas”. (1667).

[76] A.M. Ostrowski.“On two problems in abstract algebra connected with Horner’s rule”. In Studies in Math. and Mech. presented to Richard von Mises Academic Press (1954) 40–48.

[77] P. Philippon.“Sur des hauteurs alternatives, I”. Math. Ann. 289 (1991) 255-283.

[78] P. Philippon. “Sur des hauteurs alternatives, II”. Ann. Inst. Fourier, Grenoble 44, 2 (1994) 1043– 1065.

[79] P. Philippon.“Sur des hauteurs alternatives, III”. To appear in J. Math. Pures Appl..

[80] D.A. Plaisted.“Sparse Complex Polynomials and Polynomial Reducibility”. J. of Comput. Syst. Sci. 14 (1977) 210–221.

[81] R. Pollack, M.F. Roy. “ On the number of cells defined by a set of polynomials”. C.R. Acad. Sci. Paris 316 (1991) 573–577.

[82] J. Renegar. “On the Worst-Case Arithmetic Complexity of Approximating Zeros of Polynomials”. J. of Complexity 3 (1987) 90–113

[83] H. Riesel. “Prime Numbers and Computer Methods for Factorization”. Birkhäuser Progress in Math. 57 (1985).

[84] J. Sabia and P. Solernó. “Bounds for traces in complete intersections and degrees in the Nullstellensatz”. To appear in AAECC Journal ( 1993 ).

[85] F. Santos. “ Geometría Combinatoria de Curvas Algebraicas y Diagramas de Delaunay en el plano ”. Tesis, U. de Cantabria (1995).

[86] J.T. Schwartz. “Fast Probabilistic Algorithms for Verification of Polynomial Identities”.J. of the ACM 27, (1980), 701–717.

[87] T. Schneider. “Einführung in die transzendenten Zahlen”. Springer-Verlag, Berlin ( 1957 ).

[88] A. Schonhage, A. F.W. Grotefeld, E. Vetter. “Fast Algorithms (A Multitape Turing machine Implementation)” . B. I. Wissenschaftverlag (1994).

[89] M. Shub, S. Smale. “Complexity of Bézout’s theorem I : Geometric aspects”. J. Am. Math. Soc., Vol. 6, No. 2 (1993) 459–501

[90] M. Shub, S. Smale. “Complexity of Bézout’s theorem V: Polynomial time”. Theor. Comp. Sci., 133 (1994) 141–164 [91] M. Shub, S.Smale. “On the Intractability of Hilbert’s Nullstellensatz and an algebraic version of

“NP=P ?”. Preprint of IBM Research Division RC 19624 6/23/94 (1994).

[92] S. Smale. “On the Topology of Algorithms, I”. J. of Complexity, 3 (1987) 81–89.

[93] S. Smale.“On the Efficiency of Algorithms of Analysis”. Bull of the AMS 13, N. 2 (1985) 87 –121.

[94] V. Strassen. “Berechnung und Programm I”. Acta Inform., 1 (1972) 320–334.

[95] V. Strassen. “Polynomials with rational coefficients which are hard to compute”, SIAM J. Comput. 3 (1974) 128–149.

[96] V. Strassen. “Vermeidung von Divisionen”, Crelle J. Reine Angew. Math. 264 ( 1973) 184–202.

[97] V. Strassen. “Algebraic Complexity Theory”. In Handbook of Theoretical Computer Science, Elsevier, ch. 11 ( 1990 ) 634–671.

[98] B. Sturmfels. “Some Applications of Affine Gale Diagrams to Polytopes with Few Vertices.” SIAM J. Disc. Math., Vol. 1, No. 1 (1988) 121–133

[99] B. Sturmfels. “Sparse Elimination Theory”.In Computational Algebraic Geometry and Commutative Algebra”, Proc. of the Cortona Conf. on Comp. Algebraic Geometry and Commutative Algebra, D. Eisenbud and L. Robbiano (eds.). Symposia Matematica, vol. XXXIV, Istituto Nazionale di Alta Matematica, Cambridge University Press (1993) 264–298.

[100] B. Sturmfels. “Gröbner Bases of Toric Varieties.” Tohoku Math. J., 43 (1991) 249–261.

[101] A. C.C. Yao. “On Paralell Computation for the Knapsack problem”. J. of the ACM, vol. 29, No. 3 (1982) 898–903.

[102] R. Zippel. “Interpolating Polynomials from their Values”. J. Symbol. Comput., 9 (1990) 375–403