\documentstyle[ejs-article]{article}
% --------------------------------------------------

\typeout{Environments, }

\newtheorem{proposition}{Proposition}
\newtheorem{definition}[proposition]{Definition}
\newtheorem{notation}[proposition]{Notation} 
\newtheorem{algorithm}[proposition]{Algorithm}
\newtheorem{theorem}[proposition]{Theorem}
\newtheorem{proof}[proposition]{Proof} 
\newtheorem{corollary}[proposition]{Corollary} 
\newtheorem{lemma}[proposition]{Lemma}
\newtheorem{remark}[proposition]{Remark} 
\newtheorem{observation}[proposition]{Observation} 
\newtheorem{main}[proposition]{Main Theorem} 
\newtheorem{problem}{Problem}

\newcommand{\pref}[1] {{\rm (\ref{#1})}}
 
\renewcommand{\theenumi}{\roman{enumi}}
\renewcommand{\labelenumi}{\theenumi)}

% --------------------------------------------------

\newcommand{\prf}{\spar\noindent {\em Proof}.-- \ } 
\newcommand{\cqfd}{\hfill\vbox{\hrule height 5pt width 5pt }\bigskip} 
% --------------------------------------------------

\typeout{Abbreviations, }

\newcommand{\slp} {straight--line program}
\newcommand{\slps} {straight--line programs}

% --------------------------------------------------

\typeout{Sets, }

% N, Z, Q, R, C, K, P with double bar on left side

\def \N{{\rm I\kern -2.1pt N\hskip 1pt}} 
\def \Z{{\ifm{{\rm Z\!\!Z}}{${\rm Z\!\!Z}$}}}
\def \R{{\rm I\kern -2.2pt R\hskip 1pt}} 
\def \K {{\rm I\kern -2.1pt K\hskip 1pt}} 
\def \F {{\rm I\kern -2.1pt F\hskip 1pt}} 
\def \P{{\rm I\kern -2.2pt P\hskip 1pt}} 
\def \Fp {\F_p}

\newcommand{\Barq}  {\vrule height0.65em width0.05em depth0em \,}
\newcommand{\Q}        {\ifm {\mbox{\rm Q}\hspace{-0.54em}\Barq\>\;}
                             {$\mbox{\rm Q}\hspace{-0.54em}\Barq\>\;$}}
\newcommand{\C}        {\ifm {\mbox{\rm C}\hspace{-0.45em}\Barq\>}
                             {$\mbox{\rm C}\hspace{-0.45em}\Barq\>$}}

% --------------------------------------------------
\newtheorem{example}[proposition]{Example}

% -------------------------------------------------------------------
\begin{document}
\Issue{2}{1}{1--23}{1997}

\HeadingAuthor{J. Heinz et al.}
\HeadingTitle{Complexity of parametric elimination}

\Title{The intrinsic complexity of parametric elimination methods}
\Author {J. Heintz\inst{1,2} \And G. Matera\inst{2,3}  \And  L. M. Pardo\inst{1} \And R. Wachenchauzer\inst{4}}

\institute{Depto. de Matem\'aticas, Est. y Comp., Facultad de
Ciencias, Universidad de Cantabria, E-39071 SANTANDER, Spain.\\
 {\tt heintz@matsun1.matesco.unican.es}
\and Depto. de Matem\'aticas, FCEyN, Universidad de Buenos Aires,
Ciudad Universitaria, Pab. I, (1428) BUENOS AIRES, Argentina.
{\tt gmatera@dm.uba.ar}. 
\and Instituto de Ciencias, Universidad Nacional de Gral.
Sarmiento, Roca 850, (1663) San Miguel - Pcia. de Buenos Aires,
Argentina.
\and Departamento de Computaci\'on,  FCEyN, Universidad de Buenos
Aires, 
Ciudad Universitaria, Pab. I, (1428) BUENOS AIRES, Argentina.\\
{\tt rosita@dc.uba.ar}.} 
\institutename

% --------------------------------------------------------------------------
\begin{abstract}
This paper is devoted to the complexity analysis of a particular property,
called {\em geometric robustness} owned by all known symbolic methods of 
parametric polynomial equation solving (geometric elimination).
It is shown that {\em any} parametric elimination procedure which owns this
property must necessarily have an exponential sequential time complexity 
even if highly performant data structures 
(as e.g. the \slp\ encoding of polynomials) are used.
The paper finishes with the motivated introduction of a new non-uniform
complexity measure for zero-dimensional polynomial equation systems, called
{\em elimination complexity}.
\end{abstract}
\smallskip

{\bf Keywords.} {\small Polynomial system solving, elimination, complexity.}

\Ack{Research was partially supported by the following
Argentinian and Spanish grants:UBA-CYT.EX.001, PIP CONICET 4571, DGICYT PB96--0671--C02--02.}
 
% -------------------------------------------------------------------
\Body

\section{Introduction}\label{sec-intro}
Modern algebraic geometry started about 200 years ago as {\em algorithmic}
algebraic geometry, and, more precisely, as algorithmic elimination theory.
The motivation for the creation of such a field was the search for methods
which allow to find the {\em real} solutions of a polynomial equation system.
Nevertheless, the very origin of algebraic geometry was given by the
observation that real root finding is a rather infeasible task without a
previous study of the behaviour of the {\em complex}
solutions of polynomial equation systems. This observation was first made by
Euler and B\'ezout and then extended to a general theory by a long list of
geometers of the last century.
This list includes names as Jacobi, Sylvester, Kronecker, M. Noether,
Hilbert (the creator of modern commutative algebra), Castelnuovo, Bertini,
Enriques.


Despite the orientation of modern algebraic geometry toward a new structural view
of the field, in the last twenty years a new community of algebraic
geometers doing symbolic computation splitted out of the mainstream. The
intention of this community to bring back algebraic geometry to its origin
(and to introduce also new aspects like efficient polynomial equation
solving for industrial applications) must be praised highly.
On the other hand the (mainly rewriting based) computational approach used
by this community is far too simple minded for the difficult task of
efficient, i.e. real world polynomial equation solving. An important
drawback of this approach consists in the almost total absence of todays
skill in algorithmics and data structure manipulation as well as the
unawareness of modern programming techniques coming from software
engineering. There is no place here to describe in detail the advances and
weaknesses of symbolic computation (more precisely: computer algebra)
techniques applied to elimination theory. 
For an overview about rewriting based methods (Gr\"obner
basis techniques) we refer to the books \cite{BeWe93}, 
\cite{Mishra93}, \cite{CoLiOS92}
(these books include also motivations and historical considerations).
The state of the art in sparse techniques can be found in \cite{Emiris96}.
Finally the seminumerical approach to elimination theory is described in 
the book \cite{BlCuShSm97} and the surveys
\cite{HeMo93}, \cite{Pardo95}, \cite{Heintz96} and in the
research papers \cite{GiHeMoMoPa97}, \cite{GiHaHeMoMoPa97}
and \cite{BaGiHeMaMb97}.


It is well known that there exists no polynomial time geometric
or algebraic elimination procedure if dense encoding of polynomials
is used as basic data structure 
(see e.g. \cite{MaMe82}, \cite{HeMo93}, \cite{Pardo95}).
One may ask whether this conclusion remains still true for
elimination  procedures based on the
more succinct straight--line program encoding of polynomials
as fundamental data structure 
(see e.g. \cite{HeMo93}, \cite{Pardo95}, \cite{BlShSm89}).

 \dots


\subsection{Flat families of elimination problems}\label{subsec11}

Let $k$ be an infinite and perfect field
with algebraic closure $\bar{k}$ and let

\dots


% ------------------------------------------------------------------- % page 11

\subsection{A particular flat family of 1-dimensional elimination
problems}

\dots

The discussion of the previous example
shows that the objective of
a polynomial time procedure for geometric (or algebraic) elimination can
not be reached following a evolutionary way, i.e. constructing improvements
of known elimination methods.

It was fundamental in our argumentation above that our notion of {\em
geometrically robust parametric elimination procedure} excludes branchings in the
output program. This suggests that any polynomial time elimination
algorithm (if there exists one) must have a huge topological complexity.
Thus hypothetical efficiency in geometric elimination seems to imply
complicated casuistics.

\begin{theorem}
For any $n\in\N$ there exists a one-dimensional elimination problem
depending on one parameter and $2n+1$ variables, having input length $O(n)$
such that the following holds:
any geometrically robust parametric elimination procedure which solves this problem
produces an output circuit of size at least $2^{n\over 2}-3$ (i.e. of
exponential size in the input length).
\end{theorem}


\section{On the complexity of geometric elimination procedures in
the unrestricted non-uniform mo\-del}

Let us now analyze from a general non-uniform point of view how the
seminumerical elimination procedure
designed in \cite{GiHeMoMoPa97} and \cite{GiHaHeMoMoPa97}
works on a given flat family of zero-dimensional elimination
problems.

\dots


\subsection{A particular flat family of zero-dimensional elimination
problems}

\dots


% -------------------------------------------------------

\subsection{The elimination complexity of a zero-dimensional
polynomial equation system}


% -------------------------------------------------------------------

\begin{thebibliography}{10}

\bibitem{BaGiHeMaMb97}
B.~Bank, M.~Giusti, J.~Heintz, and G.~Mbakop.
\newblock Polar Varieties and Efficient Real Equation Solving: The Hypersurface
  Case.
\newblock {\em J. of Complexity\/}, {\bf vol.~13~(1)}:pp.~5--27, 1997.

\bibitem{BaSt83}
W.~Baur and V.~Strassen.
\newblock The complexity of partial derivatives.
\newblock {\em Theoret. Comp. Sci.\/}, {\bf vol.~22}:pp.~317--330, 1983.

\bibitem{BlCuShSm97}
L.~Blum, F.~Cucker, M.~Shub, and S.~Smale.
\newblock Complexity and Real Computation.
\newblock preprint, 1997.

\bibitem{BlShSm89}
L.~Blum, M.~Shub, and S.~Smale.
\newblock On a theory of computation and complexity over the real numbers:
  {NP}-completeness, recursive functions and universal machines.
\newblock {\em Bull. of the AMS\/}, {\bf vol.~21~(1)}:pp.~1--46, 1989.

\bibitem{BuClSh97}
P.~B\"urgisser, M.~Clausen, and M.~{Amin Shokrollahi}.
\newblock {\em Algebraic Complexity Theory\/}, vol. 315 of {\em Grundlehren der
  mathematischen Wissenschaften\/}.
\newblock Springer, 1997.

\bibitem{CoLiOS92}
D.~Cox, J.~Little, and D.~O'Shea.
\newblock {\em Ideals, Varieties, and Algorithms: an introduction to
  computational algebraic geometry and commutative algebra\/}.
\newblock Undergraduate Texts in Mathematics. Springer Verlag, Berlin, 1992.

\bibitem{Emiris96}
I.~Emiris.
\newblock On the Complexity of Sparse Elimination.
\newblock {\em J.\ Complexity\/}, {\bf vol.~12}:pp.~134--166, 1996.

\bibitem{Gathen86}
J.~von~zur Gathen.
\newblock Parallel arithmetic computations: a survey.
\newblock In B.~R.~J. Gruska and J.~Wiedermann, eds., {\em Proceedings of the
  12th Symposium on Mathematical Foundations of Computer Science\/}, vol. 233
  of {\em LNCS\/}, pp. 93--112. Springer, Bratislava, Czechoslovakia, August
  1986.

\bibitem{Gathen93}
J.~von~zur Gathen.
\newblock Parallel Linear Algebra.
\newblock In J.~H. Reif, ed., {\em Synthesis of Parallel Algorithms\/}. Morgan
  Kaufmann, 1993.

\bibitem{GiHaHeMoMoPa97}
M.~Giusti, K.~H{\"a}gele, J.~Heintz, J.~E. Morais, J.~L. {Monta\~na}, and L.~M.
  Pardo.
\newblock Lower Bounds for Diophantine Approximation.
\newblock In {\em Proceedings of MEGA'96\/}, vol. 117,118, pp. 277--317.
  Journal of Pure and Applied Algebra, 1997.

\bibitem{GiHeMoMoPa97}
M.~Giusti, J.~Heintz, J.~E. Morais, J.~Morgenstern, and L.~M. Pardo.
\newblock Straight--Line Programs In Geometric Elimination Theory.
\newblock {\em to appear in J. of Pure and App. Algebra\/}, pp. 1--46, 1997.

\bibitem{Heintz96}
J.~Heintz.
\newblock The Project TERA: the Comeback of Oblomov in Computer Science.
\newblock {\em SAC Newsletter\/}, {\bf vol.~1}, nov 1996.

\bibitem{HeMo93}
J.~Heintz and J.~Morgenstern.
\newblock On the intrinsic complexity of elimination theory.
\newblock {\em J. of Complexity\/}, {\bf vol.~9}:pp.~471--498, 1993.

\bibitem{MaMe82}
E.~Mayr and A.~Meyer.
\newblock The complexity of the word problem for commutative semigroups.
\newblock {\em Adv. in Math.\/}, {\bf vol.~46}:pp.~305--329, 1982.

\bibitem{Mishra93}
B.~Mishra.
\newblock {\em Algorithmic Algebra\/}.
\newblock Springer Verlag, New York, 1993.
\newblock ISBN 0-387-94090-1.

\bibitem{Mumford88}
D.~Mumford.
\newblock {\em The Red Book of Varieties and Schemes\/}, vol. 1358 of {\em
  LNM\/}.
\newblock Springer, Berlin, first edition, 1988.

\bibitem{Pardo95}
L.~M. Pardo.
\newblock How lower and upper complexity bounds meet in elimination theory.
\newblock In G.~Cohen, H.~Giusti, and T.~Mora, eds., {\em Applied Algebra,
  Algebraic Algorithms and Error Corecting Codes. Proceedings of {AAECC-11}\/},
  vol. 948 of {\em LNCS\/}. Springer, 1995.

\bibitem{Shafarevich84}
I.~Shafarevich.
\newblock {\em Basic algebraic geometry\/}.
\newblock Graduate Texts in Mathematics. Springer-Verlag, 1984.

\bibitem{Strassen73A}
V.~Strassen.
\newblock Die Berechnungskomplexit{\"a}t von elementarsymmetrischen\\ Funktionen
  und von Interpolationspolynomen.
\newblock {\em Numer. Math.\/}, {\bf vol.~2}: pp.~238--251, 1973.

\bibitem{BeWe93}
V.~Weispfenning and T.~Becker.
\newblock {\em Groebner bases: a computational approach to commutative
  algebra\/}, vol. 141 of {\em Graduate Texts in Mathematics: readings in
  mathematics\/}.
\newblock Springer, 1993.

\end{thebibliography}


\end{document}

% --------------------------------------------------------------------------