Wir beschäftigen uns mit Problemen der algorithmischen Gruppentheorie und untersuchen dabei die Komplexität von komprimierten Versionen des Wortproblems und des Konjugationsproblems für endlich erzeugte Gruppen. Das Wortproblem fragt für eine feste, endlich erzeugte Gruppe ob ein gegebenes Wort über der Erzeugermenge das neutrale Element der Gruppe repräsentiert. Wir betrachten das gegebene Wort jedoch in einer komprimierten Form, als Straight-line Program (SLP) und untersuchen die Komplexität dieses Problems, das wir \'komprimiertes Wortproblem\' nennen. SLPs sind kontextfreie Grammatiken, die genau einen String erzeugen. Die Eingabegröße ist dabei stets die Größe des gegebenen SLPs. Eine Hauptmotivation ist dabei, dass für eine feste endlich erzeugte Gruppe das Wortproblem ihrer Automorphismengruppe durch eine Turingmaschine in Polynomialzeit auf das komprimierte Wortproblem der Gruppe selbst reduzierbar ist. Wir untersuchen das komprimierte Wortproblem für die verbreiteten Gruppenerweiterungen HNN-Erweiterungen (amalgamierte Produkte und Graphprodukte) und können zeigen, dass sich Instanzen des komprimierten Wortproblems von einer Turingmaschine in Polynomialzeit auf Instanzen des komprimierten Wortproblems der Basisgruppe (respektive Basisgruppen und Knotengruppen) reduzieren lassen. Weiterhin zeigen wir, dass das komprimierte Wortproblem für endlich erzeugte nilpotente Gruppen von einer Turingmaschine in Polynomialzeit entscheidbar ist. Wir betrachten außerdem eine komprimierte Variante des Konjugationsproblems. Das unkomprimierte Konjugationsproblem fragt für zwei gegebene Wörter über den Erzeugern einer festen endlich erzeugten Gruppe, ob sie in dieser Gruppe konjugiert sind. Beim komprimierten Konjugationsproblem besteht die Eingabe aus zwei SLPs und es wird gefragt, ob die beiden Wörter die von den SLPs erzeugt werden in der Gruppe konjugierte Elemente präsentieren. Wir konnten zeigen, dass sich das komprimierte Konjugationsproblem für Graphgruppen in Polynomialzeit entscheiden lässt. Weiterhin haben wir das Wortproblem der äußeren Automorphismengruppen von Graphprodukten endlich erzeugter Gruppen untersucht. Durch den engen Zusammenhang des komprimierten Konjugationsproblems einer Gruppe mit dem Wortproblem der äußeren Automorphismengruppe konnten wir zeigen, dass sich das Wortproblem der äußeren Automorphismengruppe eines Graphprodukts von endlich erzeugten Gruppen durch eine Turingmaschine in Polynomialzeit auf Instanzen von simultanen komprimierten Konjugationsproblemen der Knotengruppen und Instanzen von komprimierten Wortproblemen der Knotengruppen reduzieren lässt. Als Anwendung gelten obige Resultate auch für right-angled Coxetergruppen und Graphgruppen, da beide spezielle Graphprodukte sind. So folgt beispielsweise, dass das komprimierte Wortproblem einer right-angled Coxetergruppe in Polynomialzeit entscheidbar ist.

Wir beschäftigen uns mit Problemen der algorithmischen Gruppentheorie und untersuchen dabei die Komplexität von komprimierten Versionen des Wortproblems und des Konjugationsproblems für endlich erzeugte Gruppen. Das Wortproblem fragt für eine feste, endlich erzeugte Gruppe ob ein gegebenes Wort über der Erzeugermenge das neutrale Element der Gruppe repräsentiert. Wir betrachten das gegebene Wort jedoch in einer komprimierten Form, als Straight-line Program (SLP) und untersuchen die Komplexität dieses Problems, das wir \''komprimiertes Wortproblem\'' nennen. SLPs sind kontextfreie Grammatiken, die genau einen String erzeugen. Die Eingabegröße ist dabei stets die Größe des gegebenen SLPs. Eine Hauptmotivation ist dabei, dass für eine feste endlich erzeugte Gruppe das Wortproblem ihrer Automorphismengruppe durch eine Turingmaschine in Polynomialzeit auf das komprimierte Wortproblem der Gruppe selbst reduzierbar ist. Wir untersuchen das komprimierte Wortproblem für die verbreiteten Gruppenerweiterungen HNN-Erweiterungen (amalgamierte Produkte und Graphprodukte) und können zeigen, dass sich Instanzen des komprimierten Wortproblems von einer Turingmaschine in Polynomialzeit auf Instanzen des komprimierten Wortproblems der Basisgruppe (respektive Basisgruppen und Knotengruppen) reduzieren lassen. Weiterhin zeigen wir, dass das komprimierte Wortproblem für endlich erzeugte nilpotente Gruppen von einer Turingmaschine in Polynomialzeit entscheidbar ist. Wir betrachten außerdem eine komprimierte Variante des Konjugationsproblems. Das unkomprimierte Konjugationsproblem fragt für zwei gegebene Wörter über den Erzeugern einer festen endlich erzeugten Gruppe, ob sie in dieser Gruppe konjugiert sind. Beim komprimierten Konjugationsproblem besteht die Eingabe aus zwei SLPs und es wird gefragt, ob die beiden Wörter die von den SLPs erzeugt werden in der Gruppe konjugierte Elemente präsentieren. Wir konnten zeigen, dass sich das komprimierte Konjugationsproblem für Graphgruppen in Polynomialzeit entscheiden lässt. Weiterhin haben wir das Wortproblem der äußeren Automorphismengruppen von Graphprodukten endlich erzeugter Gruppen untersucht. Durch den engen Zusammenhang des komprimierten Konjugationsproblems einer Gruppe mit dem Wortproblem der äußeren Automorphismengruppe konnten wir zeigen, dass sich das Wortproblem der äußeren Automorphismengruppe eines Graphprodukts von endlich erzeugten Gruppen durch eine Turingmaschine in Polynomialzeit auf Instanzen von simultanen komprimierten Konjugationsproblemen der Knotengruppen und Instanzen von komprimierten Wortproblemen der Knotengruppen reduzieren lässt. Als Anwendung gelten obige Resultate auch für right-angled Coxetergruppen und Graphgruppen, da beide spezielle Graphprodukte sind. So folgt beispielsweise, dass das komprimierte Wortproblem einer right-angled Coxetergruppe in Polynomialzeit entscheidbar ist.

Diese Arbeit beinhaltet {\it geometrische Algorithmen} zur L\"osung reeller polynomialer Gleichungssysteme mit rationalen Koeffizienten, wobei die Polynome eine reduzierte regul\"are Folge bilden (vgl. Abschnitt \ref{abschgeo}). Unter reellem L\"osen verstehen wir hier die Bestimmung eines Punktes in jeder Zusammenhangskomponente einer kompakten glatten reellen Variet\"at $V:=W \cap \R^n$.\\ Im Mittelpunkt steht die Anwendung des f\"ur den algebraisch abgeschlossenen Fall ver\"offentlichten symbolischen geometrischen Algorithmus nach \cite{gh2} und \cite{gh3}. Die Berechenungsmodelle sind {\em Straight--Line Programme} und {arithmetische Netzwerke} mit Parametern in $\; \Q$. Die Input--Polynome sind durch ein Straight--Line Programm der Gr\"o{\ss}e $L$ gegeben. Eine geometrische L\"osung des Input--Glei\-chungs\-sys\-tems besteht aus einem primitiven Element der Ringerweiterung, welche durch die Nullstellen des Systems beschrieben ist, aus einem mininalen Polynom dieses primitiven Elements, und aus den Parametrisierungen der Koordinaten. Diese Darstellung der L\"osung hat eine lange Geschichte und geht mindestens auf Leopold Kronecker \cite{kron} zur\"uck. Die Komplexit\"at des in dieser Arbeit begr\"undeten Algorithmus erweist sich als linear in $L$ und polynomial bez\"uglich $n, d, \delta$ bzw. $\delta \;'$, wobei $n$ die Anzahl der Variablen und $d$ eine Gradschranke der Polynome im System ist. Die Gr\"o{\ss}en $\delta$ und $\delta \; '$ sind geometrische Invarianten, die das Maximum der {\em Grade des Inputsystems} und geeigneter {\em polarer Variet\"aten} repr\"asentieren (bzgl. des ({\em geometrischen}) Grades vgl. \cite{he}). Die Anwendung eines Algorithmus \"uber den komplexen Zahlen auf das L\"osen von polynomialen Gleichungen im Reellen wird durch die Einf\"urung polarer Variet\"aten m\"oglich (vgl. \cite{bank}). Die polaren Variet\"aten sind das Kernst\"uck und das vorbereitende Werzeug zur effizienten Nutzung des oben erw\"ahnten geometrischen Algorithmus. Es wird ein inkrementelles Verfahren zur Auffindung reeller Punkte in jeder Zusammenhangskomponente der Nullstellenmenge des Inputsystems abgeleitet, welches einen beschr\"ankten glatten (lokalen) vollst\"andigen Durchschnitt in $\R^n$ beschreibt. Das Inkrement des Algorithmus ist die Kodimension der polaren Variet\"aten. Die Haupts\"atze sind Satz $\ref{theorem12}$ auf Seite $\pageref{theorem12}$ f\"ur den Hyperfl\"achenfall, und Satz $\ref{theoresult}$ auf Seite $\pageref{theoresult}$, sowie die Aussage in der Einf\"uhrung dieser Arbeit, Seite $\pageref{vollres}$ f\"ur den vollst\"andigen Durchschnitt. / This dissertation deals with {\em geometric algorithms} for solving real multivariate polynomial equation systems, that define a reduced regular sequence (cf. subsection $\ref{abschgeo}$). Real solving means that one has to find at least one real point in each connected component of a real compact and smooth variety $V := W \cap \R^n$. \\ The main point of this thesis is the use of a complex symbolic geometric algorithm, which is designed for an algebraically closed field and was published in the papers \cite{gh2} and \cite{gh3}. The models of computation are {\em straight--line programms} and {\em arithmetic Networks} with parameters in $\; \Q$. Let the polynomials be given by a division--free straight--line programm of size $L$. A geometric solution for the system of equations given by the regular sequence consists in a {\em primitiv element} of the ring extension associated with the system, a minimal polynomial of this primitive element and a parametrization of the coordinates. This representation has a long history going back to {\em Leopold Kronecker} \cite{kron}. The time--complexity of our algorithms turns out to be linear in $L$ and polynomial with respect to $n, d, \delta$ or $\delta '$, respectively. Here $n$ denotes the number of variables, $d$ is an upper bound of the degrees of the polynomials involved in the system, $\delta$ and $\delta '$ are geometric invariants representing the maximum of the {\em affine (geometric) degree} of the system under consideration and the affine (geometric) degree of suitable {\em polar varieties} (cf. \cite{he} for the ({\em geometric}) degree). The application of an algorithm running in the complex numbers to solve polynomial equations in the real case becomes possible by the introduction of polar varieties (cf. \cite{bank}). The polar varieties introduced for this purpose prove to be the corner--stone and the preliminary tool for the efficient use of the geometric algorithm mentioned above. An incremental algorithm is designed to find at least one real point on each connected component of the zero set defined by the input under the assumption that the given semialgebraic set $V = W \cap \R^n$ is a bounded, smooth (local) complete intersection manifold in $\R^n$. The increment of the new algorithm is the codimension of the polar varieties under consideration. The main theorems are Theorem $\ref{theorem12}$ on page $\pageref{theorem12}$ for the hypersurface case, and Theorem $\ref{theoresult}$ on page $\pageref{theoresult}$ for the complete intersection as well as the statement in the introduction of this thesis on page $\pageref{vollres}$.