\documentclass[12pt,twoside]{article}

\usepackage{amssymb}
\usepackage[german]{babel}
\usepackage{epic}
\usepackage{latexsym}
\usepackage{bezier}

\pagestyle{myheadings}
\newtheorem{theorem}{Satz}
\newtheorem{corollary}[theorem]{Korollar}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{proposition}[theorem]{Proposition}

\parindent=0pt
\parskip=1em
\setlength{\textwidth}{14cm}

\def\C{{\mathbb C}}
\def\R{{\mathbb R}}
\def\F{{\mathbb F}}
\def\N{{\mathbb N}}
\def\det{{\mathrm{det}}}
\def\iff{{\Leftrightarrow}}
\def\graph{{\mathrm{graph}}}

\begin{document}
\markboth{}{{\sc S\'eminaire Lotharingien de Combinatoire} {\rm S36a (18pp.)}}
%\bibliographystyle{plain}
\phantom{...}
\vspace{0.3cm}
\begin{center}
{\Large\bf Algebraische Komplexit\"atstheorie I}
\end{center}
\begin{center}
{\Large\bf Eine Einf\"uhrung}
\end{center}
\begin{center}
{\sc Peter B\"urgisser, Universit\"at Z\"urich}\\
{\sc Michael Clausen, Universit\"at Bonn}
\end{center}


\vspace{1cm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Im Rahmen des 36.~Treffens des S\'eminaire Lotharingien de
Combinatoire vom 19.-22.3.96 auf Schlo\ss\ Thurnau hatten wir die 
Gelegenheit, in drei Vortr\"agen Entwicklungen der 
algebraischen Komplexit\"atstheorie vorzustellen. Die vorliegende 
Arbeit stellt eine Ausarbeitung des ersten Vortrags dar, dessen Ziel
es war, eine sanfte Einf\"uhrung in die Thematik zu vermitteln. 
Im zweiten und dritten Vortrag (siehe die nachfolgenden
Ausarbeitungen) wurden dann zwei wichtige, auch kombinatorisch 
gepr\"agte Teilgebiete der algebraischen Komplexit\"atstheorie 
mehr im Detail vorgestellt.

\section{Vorbemerkungen}

Die algorithmische L\"o\-sung von Berechnungsproblemen hat 
seit jeher zu den Haupt\-aufgaben der Mathematik geh\"ort. 
Lange Zeit basierten derartige L\"o\-sun\-gen auf einem intuitiven 
Berechenbarkeitsbegriff. Erst in der ersten H\"alfte dieses 
Jahrhunderts hat man, angeregt durch metamatematische 
Fragestellungen, intensiv nach einer allgemeinen Formalisierung des
intuitiven Berechenbarkeitsbegriffs gesucht. 

Verschiedene formale Modelle wurden vorgeschlagen, wie z.B.\ Turingmaschinen,
Re\-gistermaschinen,  While-Programme, rekursive Funktionen, 
Markov-Al\-go\-rithmen und Thue-Systeme. Diese Konzepte stellten sich aber
alle als \"aquivalent heraus, was dann zu der \"Uberzeugung f\"uhrte, 
damit eine ad\"aquate Explikation des intuitiven Berechenbarkeits- und
Algorithmenbegriffs gefunden zu haben (These von Church). 
Dies hatte und hat enorme Auswirkungen. 
Zun\"achst einmal war es jetzt m\"oglich, die algorithmische Unl\"osbarkeit von 
Problemen zu beweisen. Ber\"uhmte Beispiele sind das Halteproblem, 
das Postsche Kor\-respondenzproblem, das Wortproblem der Gruppentheorie 
oder Hilberts 10. Problem. Auf der anderen Seite hatten Kon\-zepte wie 
Turingmaschinen und While-Programme einen gro\ss en Einflu\ss\ auf die 
Ent\-wicklung der ersten Universalrechner und deren Programmierung. 

Im Zeitalter der Digitalrechner trat dann die Frage nach effizienten 
Algorithmen immer mehr in den Vordergrund. 
Manche Probleme lassen sich sehr effizient l\"osen,  
w\"ahrend andere, darunter zahlreiche praxisrelevante, 
sich allen Anstrengungen zur effizienten L\"osung widersetzten.
Diese Tatsache f\"uhrte auf die Frage nach einem tieferen Verst\"andnis der 
inh\"arenten Schwierigkeiten bei der algorithmischen L\"osung von 
Berechnungsproblemen, woraus die Komple\-xi\-t\"atstheorie entstand. 
Seither hat sich dieses Gebiet st\"urmisch
entwickelt, und es entstanden eine F\"ulle von Teildisziplinen. 
Jede dieser Disziplinen benutzt spezielle Berechnungsmodelle, wie 
z.B.\ Turingmaschinen, RAMs (Random Access Machines), Boolesche Schaltkreise,
straight-line Programme, Berechnungsb\"aume, oder VLSI-Modelle. 
Jede Berechnung in einem solchen Modell verursacht Kosten, wie 
die Anzahl der Rechenschritte einer Turingmaschine oder RAM, 
der ben\"otigte Speicherplatz, die Anzahl der Gatter in einem
Schaltkreis, die Anzahl der Befehle oder die Gr\"o\ss e der
Chipfl\"ache. Dementsprechend finden Untersuchungen in der 
Komplexit\"atstheorie immer auf der Basis eines Berechnungsmodells 
und eines gew\"ahlten Kostenma\ss es statt. 
Unter der {\em Komplexit\"at} eines Problems versteht man jeweils die 
minimalen Kosten, die zu seiner L\"osung im Rahmen des gew\"ahlten 
Berechnungsmodells erforderlich sind. 
F\"ur einen \"Uberblick \"uber viele Gebiete der Komplexit\"atstheorie
verweisen wir auf~\cite{leeu:90}.

\markboth{\hfill P.~B\"urgisser and M.~Clausen \hfill}%
{\hfill Algebraische Komplexit\"atstheorie I \hfill}

In unseren drei Vortr\"agen geht es um algebraische Komplexit\"atstheorie. 
Darunter versteht man die Untersuchung der Komplexit\"at algebraischer
Berechnungsprobleme im Rahmen algebraischer Berechnungsmodelle, 
deren wichtigste die straight-line Programme und Berechnungsb\"aume sind. 
Die algebraische Komplexit\"atstheorie entstand aus 
Fragen der numerischen Mathematik und des symbolischen Rechnens. 
Das Jahr 1954 wird oft als ihr Geburtsjahr angesehen, als n\"amlich 
Alexander Ostrowski~\cite{ostr:54} die Frage nach der Optimalit\"at der 
Hornerschen Regel zur Diskussion  stellte. 
Systematische Forschung wurde in der algebraischen Komplexit\"atstheorie 
seit Anfang der 70er Jahre betrieben;
einen ziemlich aktuellen \"Uberblick geben die Artikel 
von Strassen~\cite{stra:90} und von zur Gathen~\cite{gath:88}.
Bisher gab es nur die Monographie von Borodin und Munro~\cite{bomu:75} zu diesem Thema, 
welche vergriffen und schon lange nicht mehr auf dem neuesten Stand ist. 
Demn\"achst erscheint aber unsere umfassende Darstellung der algebraischen
Komplexit\"atstheorie in Buchform~\cite{bucs:96}.  




\section{Straight-Line Programme und Komplexit\"at}

In diesem Abschnitt wird das einfachste und zugleich wichtigste 
Berechnungsmodell der algebraischen Komplexit\"atstheorie 
vorgestellt: n\"amlich straight-line Programme. Auf der Basis dieses
Modells und einem Kostenma\ss\ k\"onnen wir dann die {\em Komplexit\"at} 
vieler (algebraischer) Berechnungsprobleme definieren. 

Grob gesprochen ist ein straight-line Programm ein Verfahren, das von bestimmten
algebrai\-schen Eingaben ausgeht (oft sind das Unbestimmte \"uber einem
K\"orper $k$) und schritt\-weise 
mittels algebraischer Operationen wie Addition, 
Subtraktion, Skalarmultiplikation, Multiplikation oder Division 
Zwischenergebnisse produziert. Einmal produzier\-te Zwischenergebnisse 
k\"onnen sp\"ater ohne Kosten wiederverwendet werden. 
Die Berechnung kann beendet werden, wenn die zu berechnenden Gr\"o\ss en 
unter den Zwischenergebnissen vorkommen. 

Die nachfolgende Definition pr\"azisiert diese Vorstellung. 

\begin{definition} 
\begin{itemize}\item[]
\item Eine {\em Eingabe} der L\"ange $n$ \"uber 
      einem K\"orper $k$ ist von der
      Form $(A;a)$ mit einer $k$-Algebra $A$ und einem $a\in A^n$. (Dabei
      stellt $A$ den Bereich dar, in dem die Berechnungen 
      stattfinden sollen.)
\item (Syntax) Ein {\em straight-line Programm}, das Eingaben der L\"ange
      $n$ \"uber $k$ erwartet, ist eine endliche Folge 
      $\Gamma=(\Gamma_1,\ldots,\Gamma_r)$ von Anweisungen der
      Form $\Gamma_i=(\omega_i;\alpha,\beta)$, falls
      $\omega_i\in\{+,-,*,/\}$ oder $\Gamma_i=(\omega_i;\alpha)$,
      falls $\omega_i\in k$. Dabei ist $k$ ein K\"orper und $-n<\alpha,\beta<i$. 
\item (Semantik) Ein straight-line Programm 
      $\Gamma=(\Gamma_1,\ldots,\Gamma_r)$ angesetzt auf die Eingabe 
      $(A;a)$ der L\"ange $n$ produziert, sofern ausf\"uhrbar, 
      eine {\em Resultatfolge} $(A;b)$
      $$b=(\underbrace{b_{-n+1},\ldots,b_0}_{:=a},b_1,\ldots,b_r),$$
      die folgenderma\ss en definiert ist: f\"ur alle $1\le i\le r$ gilt
      $$b_i=\left\{\begin{array}{ll}
                 b_{\alpha}\,\omega_i\,b_{\beta}&\mbox{falls\ }
                 \Gamma_i=(\omega_i;\alpha,\beta)\\
                  \omega_i\cdot b_{\alpha}&\mbox{falls\ } 
                  \Gamma_i=(\omega_i;\alpha).
                 \end{array}\right.$$
      (Die Ausf\"uhrbarkeit bedeutet, da\ss\ nur Divisionen durch Einheiten
       von $A$ vorkommen.) Man sagt, da\ss\ $\Gamma$ die Elemente $b_i$ 
       berechnet.
\item (Kosten) Bez\"uglich einer {\em Kostenfunktion} $c:\{+,-,*,/\}\cup k\to\N$ 
      definiert man die $c$-L\"ange eines straight-line Programms 
      $\Gamma$ als $\sum_i c(\omega_i)$. 
\item (Komplexit\"at) Die {\em Komplexit\"at} $L_A^c(F|I)$ 
      von $F\subseteq A$ modulo der Eingabemenge $I\subseteq A$ bzgl.\ $c$ 
      ist definiert als
      die minimale $c$-L\"ange eines straight-line Programms $\Gamma$, das 
      aus einer Eingabe der Form $(A;a)$ mit $a\in I^n$, $n\in\N$,
      alle Elemente von $F$ berechnet.
\end{itemize}
\end{definition}

Jede in dem gesteckten Rahmen zugelassene Berechnung liefert eine
obere Schranke f\"ur die Komplexit\"at des Berechnungsproblems. 
Insofern gibt es hier enge Verbindungen zur Computer Algebra, deren 
vornehmliche Aufgabe der Entwurf und die Implementation effizienter 
algebraischer Algorithmen ist. Die Hauptaufgabe der algebraischen 
Komplexit\"atstheorie ist die Herleitung von nichttrivialen unteren 
Schranken. Dies ist meistens ziemlich schwierig, da man ja 
gegen alle nur denkbaren Algorithmen argumentieren mu\ss, die zugelassen 
sind und das Problem l\"osen. Im g\"unstigsten Fall, wenn 
obere und untere Schranke \"ubereinstimmen, hat man einen 
{\em optimalen} Algorithmus gefunden. 

Wir illustrieren dies am Beispiel der Polynomauswertung. 

{\bf Beispiel.} Zu berechnen sei das allgemeine Polynom $n$-ten Grades
$$p:=a_0X^n+a_1X^{n-1}+\ldots+a_nX^0$$
aus den Gr\"o\ss en $a_0,\ldots,a_n,X$, die wir als Unbestimmte
\"uber einem K\"orper $k$ auffassen. 
Gerechnet werden soll im rationalen Funktionenk\"orper $A$
erzeugt durch diese Unbestimmten \"uber $k$. Ostrowski folgend z\"ahlen wir nur die 
Multiplikationen und Divisionen und betrachten die linearen 
Operationen als kostenlos. Das hei\ss t, wir verwenden die 
Kostenfunktion 
$$c(*)=c(/)=1,\  c(+)=c(-)=0,\ \forall\omega\in k : c(\omega)=0,$$
und schreiben f\"ur die resultierende {\em nichtskalare} oder
{\em Ostrowski-Komplexit\"at} statt $L_A^c$ einfach $L$.
Diese Z\"ahlung mag unrealistisch
erscheinen. Bedenken Sie aber, da\ss\ f\"ur die Ostrowski-Komplexit\"at 
erzielte untere Schranken g\"ultig bleiben, wenn man alle Operationen 
z\"ahlt!

Die Hornersche Regel zur Polynomauswertung basiert auf der ``Formel'':
$$p=(\ldots(((a_0\cdot X+a_1)\cdot X+a_2)\cdot X+a_3)\ldots)\cdot
X+a_n.$$
Tats\"achlich handelt es sich hier um ein straight-line Programm:
in einem ersten Schritt berechnen wir 
$b_1:=a_0\cdot X$; dann wird $a_1$ zu diesem Zwischenresultat
hinzuaddiert, wodurch man das zweite Zwischenresultat erh\"alt:
$b_2:=b_1+a_1$. Dieses wird dann mit $X$ multipliziert: 
$b_3:=b_2\cdot X$, usw. Indem wir $b_{-n-1}:= X$ und $b_{-i}:=a_i$ 
setzen, k\"onnen wir die Hornersche Regel wie folgt schreiben:
$$b_{2i}:=b_{2i-1}+b_{-i}\quad\mbox{und}\quad b_{2i-1}:=b_{2i-2}\cdot b_{-n-1},$$
f\"ur alle $1\le i\le n$. Die Folge der $b_i$ ist die Resultatfolge,
also die semantische Seite des zugeh\"origen straight-line Programms
$\Gamma=(\Gamma_1,\ldots,\Gamma_{2n})$,
$$\Gamma_{2i}:=(+;2i-1,-i)\quad\mbox{und}\quad
\Gamma_{2i-1}:=(*;2i-2,-n-1),$$
bez\"uglich der Eingabe $(A;(X,a_n,\ldots,a_0))$. 
Die Hornersche Regel kommt neben $n$ (kostenlosen) Additionen mit 
$n$ Multiplikationen aus. Dies liefert eine obere Schranke f\"ur die
Ostrowski-Komplexit\"at der Polynomauswertung:
$$L(\sum_{i=0}^na_iX^{n-i}|X,a_0,\ldots,a_n)\le n.$$
Ostrowski~\cite{ostr:54} hat 1954 vermutet, da\ss\ sogar Gleichheit gilt, war aber
nur in der Lage, seine Vermutung f\"ur $n\le 4$ zu beweisen. Der 
Beweis des allgemeinen Falles gelang erst 12 Jahre sp\"ater Pan~\cite{vpan:66}
mittels einer Technik, die wir heute Substitutionsmethode nennen. 
Dabei geht man, grob gesprochen, von einer hypothetischen optimalen Berechnung 
aus und trivialisiert das
erste Zwischenergebnis, das Kosten verursacht hat, durch eine
geeignete lineare Substitution der Unbestimmten. Dies f\"uhrt das 
Originalproblem in ein einfacheres Problem \"uber. Nun bleibt zu
zeigen, da\ss\ eine vollst\"andige Trivialisierung des Problems eine 
Mindestanzahl von Substitutionsschritten erfordert. Diese 
Anzahl, die typischerweise linear in der Anzahl der 
Unbestimmten ist, liefert dann eine untere Schranke.

\section{Gradschranke}

Wir diskutieren jetzt eine Methode, die es in vielen F\"allen
erlaubt, nichtlineare untere Komplexit\"atsschranken zu beweisen. 
Wieder beginnen wir mit einem konkreten Beispiel.

{\bf Beispiel.} (Mehrfache Polynomauswertung)\\
In den Anwendungen tritt nicht selten das Problem auf, ein und
dasselbe Polynom an vielen Stellen auszuwerten. 
Es soll etwa das Polynom $p$ vom Grad $n$ an
$n+1$ vorab unbekannten Stellen ausgewertet werden. Das 
l\"auft auf die Berechnung von $p(X_0),\ldots,p(X_n)$ hinaus, wo
$X_0,\ldots,X_n$ Unbestimmte \"uber $k$ sind: das hei\ss t, wir 
haben die Vandermonde-Matrix $(X_i^j)_{0\le i,j\le n}$
mit dem Vektor $(a_n,\ldots,a_0)^\top$ zu multiplizieren. 

Wenden wir $n+1$ mal die Hornersche Regel an, so ergibt sich f\"ur die 
nichtskalare Komplexit\"at dieses Pro\-blems die obere Schranke $n(n+1)$.
\"Uber\-raschen\-der\-wei\-se geht es aber viel schneller! So kommt man 
z.B.\ im Fall $k=\C$ mit $O(n\log n)$ Multiplikationen und 
insgesamt mit $O(n\log^2 n)$ arithmetischen Operationen aus
\cite{fidu:72,mobo:72,stra:73-2,bomo:74}.

Diese verbesserte obere Schranke basiert auf folgenden Fakten:
\begin{itemize}
\item Polynommultiplikation sowie Division mit Rest sind 
      in der Ostrowski-Z\"ahlung mit linearem Aufwand m\"og\-lich.
\item Berechnung der elementarsymmetrischen Polynome 
      $\sigma_1,\ldots,\sigma_n$ in $n$ Unbestimmten 
      geht mit nichtskalarem Aufwand $n\log n$.
\end{itemize}
Wir bemerken, da\ss\ bei Z\"ahlung aller Operationen h\"ochstens ein
Faktor $\log n$ hinzukommt. 

Jetzt erl\"autern wir die Grundidee der verbesserten oberen Schranke. 
Sei $q$ ungef\"ahr $n/2$. Wir berechnen die Koeffizienten des Produkts 
$\prod_0^q(X-X_i)$ (elementarsymmetrische Polynome!) und f\"uhren dann Division mit Rest durch:
$$p(X)=g(X)(X-X_0)\cdots(X-X_q)+h(X).$$
Das Restpolynom $h$ hat ungef\"ahr Grad $n/2$ und nimmt an den Stellen
$X_{i}$, $0\le i\le q$,
dieselben Werte an wie $p$. Analog berechnen wir 
bzgl.\ der anderen Variablen ein Restpolynom $h_1$ und fahren dann 
mit $h$ und $h_1$ rekursiv weiter. 

Im folgenden bereiten wir die Herleitung einer unteren Schranke 
der Gr\"o\ss en\-ord\-nung $n\log n$ f\"ur dieses Problem vor. 

Es sei $\Gamma=(\Gamma_1,\ldots,\Gamma_r)$ ein divisionsfreies
straight-line Programm, das bei Eingabe $(k[X];X)$ die Resultatfolge
$(k[X];b)$ produziert; dabei bezeichne $X=(X_1,\ldots,X_n)$ eine 
Folge von $n$ Unbestimmten \"uber $k$. F\"ur den Grad des 
$i$-ten Zwischenergebnisses $b_i$ erh\"alt man durch einfache
Rechnung:
$$\deg(b_i)\le 2^{\mu_i},$$
wo $\mu_i :=\#\{j\le i|\omega_j=*\}$ die Anzahl der Multiplikationsanweisungen des
Anfangssegments $(\Gamma_1,\ldots,\Gamma_i)$ ist. 
Wenn wir annehmen, da\ss\ $\Gamma$ das Polynom $f=b_r$ optimal im Sinne der 
Ostrowski-Z\"ahlung berechnet, so k\"onnen wir daraus auf die G\"ultigkeit der
folgenden unteren Schranke schlie\ss en: 
$$L(f|X)\ge \log\deg(f).$$
Um dies zu verallgemeinern, werden wir einer endlichen Menge von multivariaten
Polynomen einen Grad zuordnen. 
Dazu ben\"otigen wir einige Grundbegriffe aus der algebraischen Geometrie, 
an die wir zuerst erinnern wollen. 

Im folgenden bezeichne $k$ einen algebraisch abgeschlossenen K\"orper. 
Zu jeder Menge $F$ von $n$-variaten Polynomen \"uber $k$ 
geh\"ort ein Nullstellengebilde
$$Z(F):=\{\xi\in k^n \mid \forall f\in F: f(\xi)=0\}.$$
$Z(F)\subseteq k^n$ ist eine {\em affine Variet\"at}. Andererseits 
kann man jeder Teilmenge $V$ von $k^n$ ein Ideal in 
$k[X]:=k[X_1,\ldots,X_n]$ zuordnen, ihr sogenanntes {\em Verschwindungsideal}
$$I(V):=\{f\in k[X]\mid\forall\xi\in V:f(\xi)=0\}.$$
Eine affine Variet\"at $V$, die nicht als echte Vereinigung 
affiner Variet\"aten 
darstellbar ist, hei\ss t {\em irreduzibel}. Dies ist genau dann der 
Fall, wenn $I(V)$ ein Primideal, also $k[X]/I(V)$ ein
Integrit\"atsbereich ist. Eine irreduzible affine Variet\"at
$V\subseteq k^n$ besitzt eine {\em Dimension} $d\le n$, welche definiert ist 
als der Transzendenzgrad des Quotientenk\"orpers von $k[X]/I(V)$ 
\"uber $k$. 
Man kann nun einer irreduziblen Variet\"at $V\subseteq k^n$ der Dimension $d$
einen Grad zuordnen, der folgenderma\ss en
charakterisiert ist:
Fast jeder affine Teilraum $A$ von $k^n$ von komplement\"arer
Dimension $n-d$ trifft die Variet\"at $V$ in der gleichen 
endlichen Anzahl Punkte. Diese Anzahl nennt man den 
{\em (geometrischen) Grad $\deg V$}
von $V$.  

\begin{center}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setlength{\unitlength}{0.00043333in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(4500,2984)(0,-10)
\put(612,1386){\circle*{150}}
\put(2112,1836){\circle*{150}}
\put(3612,2211){\circle*{150}}
\drawline(12,1236)(12,1236)(12,1236)(4287,2436)
\drawline(312,711)      (336.121,773.389)
        (359.621,833.506)
        (382.527,891.402)
        (404.866,947.129)
        (426.667,1000.740)
        (447.957,1052.284)
        (468.763,1101.813)
        (489.113,1149.380)
        (509.033,1195.036)
        (528.552,1238.831)
        (547.697,1280.818)
        (566.496,1321.048)
        (584.976,1359.573)
        (603.164,1396.443)
        (638.775,1465.429)
        (673.550,1528.416)
        (707.707,1585.818)
        (741.467,1638.047)
        (775.050,1685.513)
        (808.675,1728.629)
        (842.562,1767.808)
        (912.000,1836.000)

\drawline(912,1836)     (967.293,1877.600)
        (1035.581,1918.077)
        (1073.447,1937.468)
        (1113.181,1956.067)
        (1154.322,1973.704)
        (1196.411,1990.207)
        (1238.987,2005.408)
        (1281.590,2019.134)
        (1323.760,2031.216)
        (1365.036,2041.484)
        (1404.958,2049.767)
        (1443.067,2055.894)
        (1512.000,2061.000)

\drawline(1512,2061)    (1580.530,2053.434)
        (1618.198,2044.628)
        (1657.580,2033.052)
        (1698.258,2019.140)
        (1739.815,2003.324)
        (1781.834,1986.041)
        (1823.899,1967.723)
        (1865.591,1948.804)
        (1906.495,1929.718)
        (1946.193,1910.899)
        (1984.268,1892.782)
        (2053.882,1860.385)
        (2112.000,1836.000)

\drawline(2112,1836)    (2170.118,1811.615)
        (2239.732,1779.218)
        (2277.807,1761.101)
        (2317.505,1742.282)
        (2358.409,1723.196)
        (2400.101,1704.277)
        (2442.166,1685.959)
        (2484.185,1668.676)
        (2525.742,1652.860)
        (2566.420,1638.948)
        (2605.802,1627.372)
        (2643.470,1618.566)
        (2712.000,1611.000)

\drawline(2712,1611)    (2780.933,1616.107)
        (2819.042,1622.234)
        (2858.964,1630.517)
        (2900.240,1640.786)
        (2942.410,1652.868)
        (2985.013,1666.596)
        (3027.589,1681.796)
        (3069.678,1698.300)
        (3110.819,1715.937)
        (3150.553,1734.536)
        (3188.419,1753.927)
        (3256.707,1794.403)
        (3312.000,1836.000)

\drawline(3312,1836)    (3381.438,1904.189)
        (3415.325,1943.366)
        (3448.950,1986.481)
        (3482.533,2033.947)
        (3516.293,2086.175)
        (3550.450,2143.576)
        (3585.225,2206.564)
        (3620.836,2275.549)
        (3639.024,2312.420)
        (3657.504,2350.945)
        (3676.303,2391.175)
        (3695.448,2433.163)
        (3714.967,2476.958)
        (3734.888,2522.614)
        (3755.237,2570.181)
        (3776.043,2619.712)
        (3797.333,2671.257)
        (3819.134,2724.867)
        (3841.473,2780.595)
        (3864.379,2838.493)
        (3887.879,2898.610)
        (3912.000,2961.000)

\put(4362,2436){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle A}$}}}}}
\put(1212,2136){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle V}$}}}}}
\put(-200,36){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle V=Z(Y-X^3+X) \subset k^2,\ \dim V =1,\ \deg V=3}$}}}}}
\end{picture}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{center}

Den Grad einer nicht notwendig irreduziblen affinen Variet\"at definiert man in
der Komplexit\"atstheorie etwas anders als es in der 
algebraischen Geometrie \"ublich ist, n\"amlich 
als die Summe der Grade der irreduziblen Komponenten von $V$.
Dies hat den Vorteil, da\ss\ die folgende Variante des B\'ezoutschen
Satzes ohne Einschr\"ankung g\"ultig ist, was 
von zentraler Bedeutung f\"ur alle Anwendungen ist. 
(F\"ur einen Beweis siehe z.B.\ \cite{bucs:96}.)

\begin{theorem}[B\'ezoutsche Ungleichung]
F\"ur affine Variet\"aten $V$, $W$ in $k^n$ gilt
$$
\deg \, V \cap W \le \deg V \cdot \deg W.
$$
\end{theorem}
Nun wollen wir den Zusammenhang zur algebraischen
Komplexit\"atstheorie herstellen. Eine zu
berechnende endliche Folge $f_1,\ldots,f_m$ von $n$-variaten 
Polynomen \"uber $k$ definiert eine polynomiale Abbildung 
$k^n\to k^m$, deren Graph eine affine Variet\"at ist, die durch die 
Gleichungen
$$Y_i-f_i(X_1,\ldots,X_n)=0\quad (1\le i\le m)$$
beschrieben ist. Definiert man den Grad von $f_1,\ldots,f_m$ als den
Grad des zugeh\"origen Graphen,
$$\deg(f_1,\ldots,f_m):=\deg \graph(f_1,\ldots,f_m),$$
so besitzt dieser Grad einige wichtige Eigenschaften.
\begin{itemize}
\item $\deg(f_1,\ldots,f_m)\le\deg(b_1,\ldots,b_r)$, falls
      $(f_1,\ldots,f_m)$ eine Teilfolge von $(b_1,\ldots,b_r)$ ist.
\item $\deg(b_1,\ldots,b_r,\alpha b_i+\beta
      b_j)=\deg(b_1,\ldots,b_r)$, falls $i,j\le r$ und $\alpha,\beta\in k$.
\item $\deg(b_1,\ldots,b_r,b_i*b_j)\le 2\deg(b_1,\ldots,b_r)$, falls
$i,j\le r$.
\end{itemize}
Die erste Eigenschaft pa\ss t sehr gut zu unserer Ausgangssituation 
bei der Herleitung unterer Komplexit\"atsschranken: Typischerweise
gehen wir von einer hypothetischen optimalen Berechnung mit 
Resultatfolge $(b_i)_{i\le r}$ aus. Wir kennen aber nur Bruchst\"ucke 
dieser Resultatfolge, eben die zu berechnenden $f_1,\ldots,f_m$. 
Die zweite Eigenschaft pa\ss t sehr gut zur Ostrowski-Z\"ahlung: 
lineare Operationen erh\"ohen den Grad nicht! Die letzte 
Eigenschaft besagt, da\ss\ eine nichtskalare Multiplikation den Grad
h\"ochstens um den Faktor zwei erh\"oht. Dies ist im wesentlichen eine 
Folge der B\'ezoutschen Ungleichung, denn 
$$\graph(b_1,\ldots,b_r,b_i*b_j)=
(\graph(b_1,\ldots,b_r)\times k)\cap Z(Y_{r+1}-Y_iY_j),$$
und $Z(Y_{r+1}-Y_iY_j)$ hat den Grad $2$. Damit sind wir bei 
der sogenannten {\em geometrischen Gradschranke} angelangt.
%%%%%%%%%%%%%%%%%%%%
\begin{theorem}[Strassen~\cite{stra:73-2}] Sind $f_1,\ldots, f_m\in
K:=k(X_1,\ldots,X_n)$, so ist
$$L(f_1,\ldots,f_m|X_1,\ldots,X_n)\ge \log\deg(f_1,\ldots,f_m).$$
Wenn $m=n$ und die $f_1,\ldots,f_n$ algebraisch unabh\"angig \"uber
$k$ sind, so gilt
$$L(f_1,\ldots,f_n|X_1,\ldots,X_n)\ge\log [K:k(f_1,\ldots,f_n)].$$
\end{theorem}
%%%%%%%%%%%%%%%%%%%%%
F\"ur die elementarsymmetrischen Polynomen $\sigma_1,\ldots,\sigma_n$ in den
Unbestimmten $X_1,\ldots,X_n$ folgt mittels Galoistheorie:
$[K:k(\sigma_1,\ldots,\sigma_n)]=|S_n|=n!.$
Die geometrische Gradschranke liefert deshalb 
$$L(\sigma_1,\ldots,\sigma_n)\ge \log(n!)\ge n(\log n-2).$$ 

Im Beispiel der mehrfachen Auswertung eines Polyoms erh\"alt man 
als Grad der K\"orpererweiterung nach leichter Rechnung $n^{n+1}$. 
Dies liefert die untere Schranke $(n+1)\log n$ und zeigt, da\ss\ der 
fr\"uher skizzierte Algorithmus bis auf einen konstanten Faktor 
optimal ist.



\section{Berechnungsb\"aume und Grad}  
 
Bis jetzt betrachteten wir nur Algorithmen, welche arithmetische 
Operationen ausf\"uhren, aber nicht die F\"ahigkeit haben, Zwischenresultate
zu vergleichen und demgem\"a\ss\ zu verzweigen. Solche Algorithmen nannten 
wir straight-line Programme. F\"ur manche Berechnungsprobleme ist 
dieses Mo\-dell aber zu eingeschr\"ankt. Zum Beispiel testet 
Gau\ss elimination Zwischenresultate auf Null, um die 
Pivotelemente zu finden. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\begin{center}
%\framebox{
\unitlength0.3cm
\begin{picture}(30,46)(-1,-1)

%
%	A- bis D-Kreise
%

\put(14,43){\circle{2}}
\put(13,42){\makebox(2,2){\footnotesize $a$}}

\put(14,40){\circle{2}}
\put(13,39){\makebox(2,2){\footnotesize $b$}}

\put(14,37){\circle{2}}
\put(13,36){\makebox(2,2){\footnotesize $c$}}

\put(14,34){\circle{2}}
\put(13,33){\makebox(2,2){\footnotesize $d$}}

%
%	Entscheidungskaesten
%

%\put(12,30){\line(1,1){2}}
%\put(12,30){\line(1,-1){2}}
%\put(16,30){\line(-1,1){2}}
%\put(16,30){\line(-1,-1){2}}
\put(13,29){\makebox(2,2.5){\footnotesize $d\stackrel{?}{=}0$}}
\put(14,30.25){\oval(6,2.5)}

%\put(7,25){\line(1,1){2}}
%\put(7,25){\line(1,-1){2}}
%\put(11,25){\line(-1,1){2}}
%\put(11,25){\line(-1,-1){2}}
\put(8,24){\makebox(2,2.5){\footnotesize $c\stackrel{?}{=}0$}}
\put(9,25.25){\oval(6,2.5)}

%
%	Linker Ast:
%	Output Box
%

\put(0,17.8){\framebox(8.2,3.2){\framebox(8,3){\footnotesize Output: $\uparrow$}}}

%
%	Mittlerer Ast:
%	Ovale Boxen,
%	Output Box
%

%\put(14,20){\oval(8,2)}
\put(10,19){\framebox(8,2){\footnotesize $b_1:=\,^{\textstyle a}/_{\textstyle
c}$}}

%\put(14,17){\oval(8,2)}
\put(10,16){\framebox(8,2){\footnotesize $b_2:=\,^{\textstyle b}/_{\textstyle 
c}$}}

\put(10,11.8){\framebox(8.2,3.2){\framebox(8,3){\footnotesize\ Output:$\!\!\begin{array}{c}
x=b_1\\ y=b_2\end{array}$}}}

%
%	Rechter Ast:
%	Ovale Boxen,
%	Output Box
%

%\put(24,20){\oval(8,2)}
\put(20,19){\framebox(8,2){\footnotesize $b_1:=\,^{\textstyle c}/_{\textstyle 
d}$}}

%\put(24,17){\oval(8,2)}
\put(20,16){\framebox(8,2){\footnotesize $b_2:=c\cdot b_1$}}

%\put(24,14){\oval(8,2)}
\put(20,13){\framebox(8,2){\footnotesize $b_3:=b\cdot b_1$}}

%\put(24,11){\oval(8,2)}
\put(20,10){\framebox(8,2){\footnotesize $b_4:=\frac{b_3-a}{b_2+d}$}}

%\put(24,8){\oval(8,2)}
\put(20,7){\framebox(8,2){\footnotesize $b_5:=a\cdot b_1$}}

%\put(24,5){\oval(8,2)}
\put(20,4){\framebox(8,2){\footnotesize $b_6:=\frac{b_5+b}{b_2+d}$}}

\put(20,-0.2){\framebox(8.2,3.2){\framebox(8,3){\footnotesize\ Output:$\!\begin{array}{c}
x=b_6\\ y=b_4\end{array}$}}}

%
%	Senkrechte Linien
%

\put(14,42){\line(0,-1){1}}
\put(14,39){\line(0,-1){1}}
\put(14,36){\line(0,-1){1}}
\put(14,33){\line(0,-1){1.5}}

\put(14,19){\line(0,-1){1}}
\put(14,16){\line(0,-1){1}}

\put(24,19){\line(0,-1){1}}
\put(24,16){\line(0,-1){1}}
\put(24,13){\line(0,-1){1}}
\put(24,10){\line(0,-1){1}}
\put(24,7){\line(0,-1){1}}
\put(24,4){\line(0,-1){1}}

%
%	Diagonale Linien
%

\put(13,29){\line(-1,-1){2.55}}
\put(9.5,27.5){\makebox(2,2){\footnotesize $=$}}

\put(8,24){\line(-1,-1){2.9}}
\put(4.5,22.5){\makebox(2,2){\footnotesize $=$}}

\put(15,29){\line(1,-1){8}}
\put(16.5,27.5){\makebox(2,2){\footnotesize $\neq$}}

\put(10,24){\line(1,-1){3}}
\put(11.5,22.5){\makebox(2,2){\footnotesize $\neq$}}
\end{picture}
%}
\end{center}
\caption{Ein Berechnungsbaum f\"ur die komplexe Division}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Ein Modell f\"ur algebraische Algorithmen, 
die auch Tests durchf\"uhren, wird durch die 
{\em algebraischen Berechnungsb\"aume} geliefert. 
Abb.~1 beschreibt schematisch einen algebraischen 
Berechnungsbaum f\"ur die komplexe Division. 
Zu einer Eingabe $(a,b,c,d)\in \R^4$ mit $c d\ne 0$
wird ein Paar $(x,y)\in\R^2$ berechnet so, da\ss\ 
$x+iy=(a+ib)/(c+id)$, d.h.\ 
$$
	x=\frac{ac+bd}{c^2+d^2}\ \ \ \mbox{und}\ \ \
	y=\frac{bc-ad}{c^2+d^2}.
$$
Falls $c=d=0$ ist, endet die Rechnung mit der Fehlermeldung 
$\uparrow$. 
Demgem\"a\ss\ ist ein algebraischer Berechnungsbaum ein bin\"arer 
Baum, der neben Eingabe- und Ausgabeknoten noch Berechnungs- und Testknoten 
enth\"alt. 
Die Berechnungsknoten haben 
Ausgrad 1 und enthalten die Instruktionen f\"ur die auszuf\"uhrenden 
arithmetischen Operationen; die Testknoten haben Ausgrad zwei und 
enthalten die Anweisungen f\"ur die Tests auf Gleichheit. 
Jede Eingabe -- in unserem Beispiel jedes $4$-Tupel $(a,b,c,d)$ 
reeller Zahlen -- 
definiert einen eindeutig bestimmten Pfad 
von der Wurzel zu einem Blatt in diesem
Baum. Die Ausgabe ist eine Teilmenge der berechneten 
Zwischenresultate, gegebenenfalls zusammen mit der Information
in welchem Blatt des Baums man gelandet ist. 
Manchmal erlaubt man auch Tests ``$b_i \le b_j$'' auf kleiner-gleich, was 
wir aber in diesem Abschnitt nicht betrachten wollen.

An dieser Stelle ist eine grunds\"atzliche 
Bemerkung \"uber die Beziehung zwischen straight-line Programmen und
Berechnungsb\"aumen am Platz. F\"ur fast alle Eingaben eines Berechnungsbaumes 
wird derselbe Pfad im Baum durchlaufen. Dieser ``generische Pfad'' 
ist im wesentlichen dadurch charakterisiert, da\ss\ immer der 
$\ne$-Verzweigung gefolgt wird. (In unserem Beispiel ist das 
der rechte Pfad.)
Die arithmetischen Operationen
entlang dieses Pfades definieren in nat\"urlicher Weise ein 
straight-line Programm, dessen 
Kosten offensichtlich eine untere Schranke f\"ur den Aufwand des 
Berechnungsbaumes darstellen. 
Eine untere Schranke f\"ur die Komplexit\"at der 
Menge der rationalen Funktionen 
$\bigg\{ \frac{ac+bd}{c^2+d^2},\frac{bc-ad}{c^2+d^2}\bigg\}$ 
in den Unbestimmten $a,b,c,d$ 
liefert deshalb auch eine untere Schranke, um die komplexe 
Division mittels Berechnungsb\"aumen zu berechnen! 
Dieser allgemeine Zusammenhang erkl\"art, warum  das 
eingeschr\"ankte Modell der straight-line Programme in der 
algebraischen Komplexit\"atstheorie so wichtig ist.

Wir betrachten nun das Problem, die 
Kettenbruchentwicklung des Quotienten $A_1/A_2$ 
zweier univariater Polynome \"uber einem K\"orper $k$ zu berechnen. 
Diese Kettenbruchentwicklung
ist durch die Folge der Quotienten $Q_1,\ldots,Q_{t-1}$ im 
Euklidschen Algorithmus 
\begin{eqnarray*}
        A_1&=&Q_1A_2+A_3\\
        A_2&=&Q_2A_3+A_4\\
           &\vdots&\\
        A_{t-2}&=&Q_{t-2}A_{t-1} + A_t,\\
        A_{t-1}&=&Q_{t-1}A_t, 
\end{eqnarray*}
gegeben, wobei das Polynom $A_t$ der gr\"o\ss te gemeinsame Teiler 
von $A_1$ und $A_2$ ist. Weil die Anzahl $t-1$ der 
Quotienten $Q_i$ sowie deren Grade nicht von vornherein bekannt 
sind, kann diese Berechnung nicht von straight-line Programmen 
durchgef\"uhrt werden. 
Hingegen kann der Euklidsche Algorithmus mit algebraischen 
Berechnungsb\"aumen beschrieben werden. 
Wir nennen die Folge $(Q_1,\ldots,Q_{t-1},A_t)$ die 
{\em Euklidsche Darstellung} von $A_1$ und $A_2$.

Was ist nun der nichtskalare Aufwand des Euklidschen Algorithmus? 
Sei im folgenden $n=\deg A_1 \ge \deg A_2$. In Abschnitt~3 erw\"ahnten 
wir, da\ss\ Division mit Rest mit linearem Aufwand m\"oglich ist. 
Da im schlimmsten Fall $n$ solche Divisionen ausgef\"uhrt werden 
m\"ussen, hat der Euklidsche Algorithmus einen quadratischen 
Aufwand $O(n^2)$. 
Ist dies nun optimal? 

Die Antwort ist nein! Unter Verwendung von Vorarbeiten von 
Lehmer~\cite{lehm:38} entwickelten 
Knuth~\cite{knut:70} und Sch\"onhage~\cite{scho:71} Anfang der 
70er Jahre ein trickreiches Verfahren, um 
den gr\"o\ss ten gemeinsamen Teiler zweier ganzer Zahlen zu berechnen. 
Deren Algorithmus l\"a\ss t sich in naheliegender Weise auf 
Polynome \"ubertragen~\cite{moen:73}. Er beruht auf  
einer rekursiven Prozedur, die
jeweils nur Anfangsst\"ucke $Q_1,\ldots,Q_{\rho}$ der Euklidschen
Darstellung berechnet, wobei die Summe der Grade der 
$Q_1,\ldots,Q_{\rho}$ etwa der halbe Grad $n/2$ von $A_1$ ist. 
Diese Prozedur liefert jeweils auch das Matrixprodukt 
$$
\left(\begin{array}{cc}
      0&1\\
      1&-Q_\rho
      \end{array} 
\right) \cdots
\left(\begin{array}{cc}
      0&1\\
      1&-Q_1
      \end{array} 
\right) .
$$
Darauf basierend kann man einen Algorithmus entwickeln, der die 
Euklidsche Darstellung, also insbesondere den gr\"o\ss ten 
gemeinsamen Teiler zweier gegebener Polynome, ungeheuer rasch 
berechnet, n\"amlich mit $O(n\log n)$ Multiplikationen oder 
Divisionen. Diese kompliziertere Aufgabe braucht also 
h\"ochstens um einen Faktor $\log n$ mehr Operationen als
die viel einfachere, zwei Polynome miteinander zu multiplizieren!

Strassen~\cite{stra:83-1} f\"uhrte eine Feinanalyse des 
Knuth-Sch\"onhage Algorithmus durch. 
Um sein Ergebnis zu erl\"autern, setzen wir einige Notationen fest.
Unter dem {\em Gradmuster} von $(Q_1,\ldots,Q_{t-1},A_t)$ wollen wir  
die Folge $d=(d_1,\ldots,d_t)$ verstehen, wobei 
$$
 d_1 :=\deg Q_1,\ldots,d_{t-1}:=\deg Q_{t-1},d_t:=\deg A_t.
$$
Offenbar gilt $\sum d_i=n=\deg A_1$. Die {\em Entropie} $H(d)$ 
der Wahrscheinlichkeits\-verteilung $\frac{1}{n} d$ ist definiert als
$$
\mbox{$ H(d) := -\sum_{d_i >0} \frac{d_i}{n}\,\log \frac{d_i}{n}$.}
$$

Strassens Ergebnis lautet nun so:

\begin{theorem} 
Der Knuth-Sch\"onhage Algorithmus berechnet die 
Euklidsche Darstellung zweier gegebener Polynome $A_1,A_2$ 
mit dem nichtskalaren Aufwand 
$$
 O(n(1+H(d))), 
$$
wobei 
$d$ das Gradmuster der Euklidschen Darstellung 
von $A_1,A_2$ bezeichnet.
\end{theorem}

Es ist einer der H\"ohepunkte der algebraischen Komplexit\"atstheorie, 
da\ss\ mit\-tels der Gradschranke die Optimalit\"at
dieses Verfahrens bewiesen werden kann! 

\begin{theorem}[Strassen~\cite{stra:83-1}]\label{ER_lb}
Es sei $k$ ein algebraisch abgeschlossener K\"orper. 
Jeder algebraische Berechnungsbaum, der die Euklidsche Darstellung
zweier Polynome
\"uber $k$ berechnet, ben\"otigt f\"ur jedes Gradmuster $d$ 
wenigstens den nicht\-ska\-laren Aufwand $n(H(d) - 2)$ f\"ur 
(Zariski) fast alle Polynome, deren Euklidsche Darstellung 
dieses Gradmuster hat.
\end{theorem}

Man beachte, da\ss\ diese Aussage sogar zeigt, da\ss\ der Knuth-Sch\"onhage 
Algorithmus optimal f\"ur {\em jedes} Gradmuster ist. 
Auch f\"ur nicht algebraisch abgeschlossene K\"orper $k$ sind untere 
Schranken bekannt, die allerdings etwas schw\"acher sind. 

Der Beweis von Satz~\ref{ER_lb} verl\"auft etwa so: man f\"uhrt 
das Problem auf die Untersuchung von straight-line Programmen zur\"uck und verwendet 
dort die Gradschranke. 
Weil sich der Grad des Graphen eines
Morphismus beim \"Ubergang zur Inversen nicht \"andert, 
wird man auf die Aufgabe gef\"uhrt, den Grad des Graphen der Abbildung
$$
 \psi: (Q_1,\ldots,Q_{t-1},A_t) \mapsto (A_1,A_2)
$$
nach unten abzusch\"atzen. 
(Dies ist gerade die Inverse der zu berechnenden Abbildung, eingeschr\"ankt 
auf die Menge der Polynompaare $(A_1,A_2)$, deren Euklidsche Darstellung das 
Gradmuster $d$ aufweist.) 

Die polynomiale Abbildung $\psi$ enth\"alt als 
homogenen Bestandteil vom h\"ochsten Grad $t$ die 
Polynommultiplikation
$$
 \psi_0 : (Q_1,\ldots,Q_{t-1},A_t) \mapsto Q_1 \cdots Q_{t-1} A_t .
$$
Indem man $\psi_0$ als eine Deformation von $\psi$ interpretiert, kann 
man beweisen, da\ss\ der Grad des Graphen von $\psi$ nicht kleiner 
als der Grad des Graphen von $\psi_0$ ist. Der letztere
kann aber leicht durch $n(H(d) - 2)$ abgesch\"atzt werden. 

Man vermutet, da\ss\ der Knuth-Sch\"onhage Algorithmus auch 
optimal f\"ur die Berechnung des gr\"o\ss ten gemeinsamen Teilers ist. 
Diese Aussage liegt aber au\ss erhalb der Reichweite der Gradschranke, 
welche nur eine lineare untere Schranke f\"ur dieses Problem liefert. 


\section{Berechnungsb\"aume und Betti-Zahlen}

Im Unterschied zu vorher untersuchen wir jetzt algebraische 
Berechnungs\-b\"au\-me \"uber dem K\"orper der reellen Zahlen $\R$, 
die auch gem\"a\ss\ kleiner-gleich
Tests verzweigen d\"urfen. 

{\bf Beispiel.} 
Beginnen wir mit dem folgenden einfachen Problem: Gegeben seien 
$n$ reelle Zahlen, zu entscheiden ist, ob diese paarweise verschieden
sind. Ein Informatiker w\"urde diese Aufgabe wohl mit einem der
g\"angigen Sortieralgorithmen l\"osen, welche nur Vergleiche $x_i < x_j$ 
und keine arithmetischen Operationen erfordern. 
Dies ist mit Gr\"o\ss enordnung $n\log n$ Vergleichen m\"oglich. 
Ein anderes Verfahren besteht darin, die Diskriminante
$\prod_{i<j} (x_i -x_j)^2$ zu berechnen, was wieder mit 
$O(n\log n)$ nicht\-skalaren Operationen m\"oglich ist, 
und das Resultat auf Null zu testen. 
Dies sind zwei sehr unterschiedliche L\"osungen des Problems:
bei der einen wird nur verglichen, bei der anderen wird bis auf einen Test 
nur gerechnet. 
Kann man mit weniger als Aufwand $n\log n$ auskommen? 

Von einem abstrakten Standpunkt aus studieren wir folgende 
al\-go\-rith\-mische Zuge\-h\"o\-rig\-keitsprobleme. 
Es sei $W$ eine feste Teilmenge von $\R^n$. 
Zu einer Eingabe $x\in \R^n$ ist zu entscheiden, ob diese in der Menge 
$W$ liegt. Als Algorithmen seien beliebige algebraische 
Berechnungsb\"aume \"uber $\R$ zugelassen. Es ist leicht 
zu sehen, da\ss\ diese Fragestellungen nur sinnvoll f\"ur Mengen $W$ ist, 
die durch Gleichungen und Ungleichungen reeller Polynome
definiert werden k\"onnen. Solche Mengen nennt man {\em semialgebraisch}.

Die Leitvorstellung ist, da\ss\ das Zugeh\"origkeitsproblem f\"ur 
Mengen mit komplizierter Topologie schwierig sein sollte. 
F\"ur das einfachste numerische Ma\ss\ der 
topologischen Kompliziertheit, n\"amlich die 
Anzahl Zusammenhangskomponenten, wurde dies durch das folgende 
Resultat von Ben-Or best\"atigt.

\begin{theorem}[Ben-Or~\cite{beno:83}]\label{ben-or}
Es sei $W$ eine semialgebraische Teilmenge von $\R^n$ mit $b_0(W)$ 
Zusammenhangskomponenten. Dann ben\"otigt jeder algebraische 
Berechnungsbaum, der das Zu\-geh\"origkeitsproblem f\"ur $W$ 
l\"ost, mindestens 
$$
   (\log 6)^{-1} \big( \log b_0(W) - n\log 3 \big)
$$
Multiplikationen, Divisionen und Vergleiche. 
\end{theorem}

In unserem Beispiel hat die Menge $W$ genau $n!$ 
Zusammenhangskomponenten: f\"ur jede Permutation $\pi$ 
beschreibt die Bedingung 
$$
x_{\pi(1)} < x_{\pi(2)} < \ldots < x_{\pi(n)}
$$
eine solche. Deshalb erhalten wir eine untere Schranke der 
Gr\"o\ss enordnung $n\log n$.
Nat\"urlich liefert Satz~\ref{ben-or} nur dann gute Ergebnisse,
wenn die Menge $W$ sehr viele Zusammenhangskomponenten hat.

Man kann das Resultat von Ben-Or als ein 
reelles Pendant zur Gradschranke interpretieren. 
\"Ahnlich wie die Gradschranke auf der B\'ezoutschen Un\-glei\-chung 
beruht, verwendet der 
Beweis von Satz~\ref{ben-or} ein tieferliegendes
Resultat von Milnor~\cite{miln:64} und Thom~\cite{thom:65}, 
welches die Summe der Bettizahlen von reellen 
algebraischen Variet\"aten durch den Grad und die Anzahl Variablen
der definierenden Polynome absch\"atzt. F\"ur den Beweis des obigen 
Satzes gen\"ugt allerdings die Absch\"atzung der nullten Bettizahl, 
welche ja gerade die Anzahl Zusammenhangskomponenten beschreibt. 

Die Schranke von Ben-Or findet z.B.\ 
Anwendungen in der algorithmi\-schen Geometrie. 
In Kombination mit einer Konstruktion von Mayr und Meyer~\cite{mame:82}
kann man damit auch eine exponentielle untere Schranke f\"ur 
das Zugeh\"origkeitsproblem zu Polynomidealen bekommen~\cite{buer:96}. 

In letzter Zeit gelang Bj\"orner, Lov\'asz und 
Yao in einer Reihe von Arbei\-ten~\cite{bjly:92,ayao:92,bjlo:92,ayao:94}
der Nachweis, da\ss\ die oben erw\"ahnte Leitvorstellung allgemeiner 
g\"ultig ist, indem sie Satz~\ref{ben-or}
auf h\"ohere Bettizahlen verallgemeinerten. 

\bigskip

Mit diesem neueren Resultat wollen wir unsere Einf\"uhrung in die 
algebraische Komplexit\"atstheorie abschlie\ss en. Wir hoffen, da\ss\ wir 
Ihnen einen kleinen Einblick in die Thematik und Methoden unseres 
Gebietes geben konnten, sowie Appetit gemacht haben auf mehr! 
Es werden ja noch zwei Themen ausf\"uhrlicher vorgestellt: 
{\em Schnelle Matrixmultiplikation und Kombinatorik} sowie 
{\em Zur Berechnungskomplexit\"at von Permanenten}. 

%\newpage

%\bibliography{/usr/home/buerg/complex/public/bib/lit-bank}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{10}

\bibitem{beno:83}
M.~Ben-Or.
\newblock Lower bounds for algebraic computation trees.
\newblock In {\em Proc.\ 15th ACM STOC, Boston}, pages 80--86, 1983.

\bibitem{bjlo:92}
A.~Bj\"orner and L.~Lov\'asz.
\newblock Linear decision trees, subspace arrangements and {M}\"obius
  functions.
\newblock {\em J.~Amer.\ Math.\ Soc.}, 7(3):677--706, 1994.

\bibitem{bjly:92}
A.~Bj\"orner, L.~Lov\'asz, and A.C. Yao.
\newblock Linear decision trees: volume estimates and topological bounds.
\newblock In {\em Proc.~24th ACM STOC}, pages 171--177, 1992.

\bibitem{bomo:74}
A.~Borodin and R.~Moenck.
\newblock Fast modular transforms.
\newblock {\em J.~Comp.~Syst.\ Sci.}, 8:366--386, 1974.

\bibitem{bomu:75}
A.~Borodin and I.~Munro.
\newblock {\em The Computational Complexity of Algebraic and Numeric Problems}.
\newblock American Elsevier, 1975.

\bibitem{buer:96}
P.~B\"urgisser.
\newblock On the parallel complexity of the polynomial ideal membership problem.
\newblock Preprint, University of Z\"urich, 1996.

\bibitem{bucs:96}
P.~B\"urgisser, M.~Clausen, and M.A. Shokrollahi.
\newblock {\em Algebraic Complexity Theory}, volume 315 of {\em {G}rundlehren
  der mathematischen {W}issenschaften}, 655~pp.
\newblock Springer Verlag, 1996.

\bibitem{fidu:72}
C.M. Fiduccia.
\newblock Polynomial evaluation via the division algorithm: the fast {F}ourier
  transform revisited.
\newblock In {\em Proc.\ 4th ACM STOC}, pages 88--93, 1972.

\bibitem{gath:88}
J.~von~zur Gathen.
\newblock Algebraic complexity theory.
\newblock {\em Ann.\ Review of Comp.\ Sci.}, 3:317--347, 1988.

\bibitem{knut:70}
D.E. Knuth.
\newblock The analysis of algorithms.
\newblock In {\em Actes du congr\`{e}s international des Math\'{e}maticiens,
  Nice}, volume~3, pages 269--274, 1970.

\bibitem{leeu:90}
J.~van Leeuwen~(ed.).
\newblock {\em Handbook of Theoretical Computer Science}, volume~A.
\newblock Elsevier Science Publishers B.~V., 1990.

\bibitem{lehm:38}
D.H. Lehmer.
\newblock Euclid's algorithm for large numbers.
\newblock {\em Amer.\ Math.\ Monthly}, 45:227--233, 1938.

\bibitem{mame:82}
E.W. Mayr and A.R. Meyer.
\newblock The complexity of the word problem for commutative semigroups and
  polynomial ideals.
\newblock {\em Adv.~Math.}, 46:305--329, 1982.

\bibitem{miln:64}
J.~Milnor.
\newblock On the {B}etti numbers of real varieties.
\newblock In {\em Proc.\ AMS}, volume~15, pages 275--280, 1964.

\bibitem{mobo:72}
R.~Moenck and A.~Borodin.
\newblock Fast modular transforms via division.
\newblock In {\em Proc.~13th Annual Symposium on Switching \& Automata Theory},
  pages 90--96, 1972.

\bibitem{moen:73}
R.T. Moenck.
\newblock Fast computation of {GCD}s.
\newblock In {\em Proc.~5th ACM STOC}, pages 142--151, 1973.

\bibitem{ostr:54}
A.M. Ostrowski.
\newblock On two problems in abstract algebra connected with {H}orner's rule.
\newblock In {\em Studies in {M}athematics and {M}echanics presented to
  {R}ichard von {M}ises}, pages 40--48. Academic {P}ress, 1954.

\bibitem{vpan:66}
V.Ya. Pan.
\newblock Methods for computing values of polynomials.
\newblock {\em Russ.\ Math.\ Surv.}, 21:105--136, 1966.

\bibitem{scho:71}
A.~Sch\"onhage.
\newblock {S}chnelle {B}erechnung von {K}ettenbruchentwicklungen.
\newblock {\em Act.\ Inf.}, 1:139--144, 1971.

\bibitem{stra:73-2}
V.~Strassen.
\newblock Die {Berechnungskomplexit\"at} von elementarsymmetrischen
  {Funktionen} und von {Interpolationskoeffizienten}.
\newblock {\em Num.~Math.}, 20:238--251, 1973.

\bibitem{stra:83-1}
V.~Strassen.
\newblock The computational complexity of continued fractions.
\newblock {\em {SIAM} J.\ Comp.}, 12:1--27, 1983.

\bibitem{stra:90}
V.~Strassen.
\newblock Algebraic complexity theory.
\newblock In J.~van Leeuwen, editor, {\em Handbook of Theoretical Computer
  Science}, chapter~11, pages 634--672. Elsevier Science Publishers B.~V.,
  Amsterdam, 1990.

\bibitem{thom:65}
R.~Thom.
\newblock Sur l'homologie des vari\'et\'es alg\'ebriques r\'eelles.
\newblock In S.S. Cairns, editor, {\em Differential and Combinatorial
  Topology}, pages 255--265. Princeton Univ.\ Press, 1965.

\bibitem{ayao:92}
A.C. Yao.
\newblock Algebraic decision trees and {E}uler characteristic.
\newblock In {\em Proc.\ 33rd {FOCS}}, 1992.

\bibitem{ayao:94}
A.C. Yao.
\newblock Decision tree complexity and {B}etti numbers.
\newblock In {\em Proc.~26th ACM STOC}, 1994.

\end{thebibliography}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}









