\documentclass[a4paper]{article}
\usepackage{amsmath,amssymb,amsfonts,german}
\sloppypar
\parindent0em
\begin{document}
\begin{center}
Zum L\"osen von Polynomgleichungen
\end{center}
Das Problem, Aussagen \"uber die (ganzzahlige) L\"osbarkeit
von Polynomgleichungen
\[
p(x_1,x_2,\ldots,x_n) = 0
\]
oder Systemen von solchen Gleichungen
\begin{eqnarray*}
p_1(x_1,x_2,\ldots,x_n) &=& 0\\
p_2(x_1,x_2,\ldots,x_n) &=& 0\\
&\vdots&\\
p_k(x_1,x_2,\ldots,x_n) &=& 0
\end{eqnarray*}
zu finden, wobei 
$p(x_1,x_2,\ldots,x_n)$ bzw. die
$p_i(x_1,x_2,\ldots,x_n)$
Polynome in den Variablen $x_1,x_2,\ldots,x_n$
mit ganzzahligen Koeffizienten sind, hat bereits den griechischen
Mathematiker \textsc{Diophantus} besch\"aftigt (3. Jh). Zu seiner Ehre spricht 
man von \textit{diophantischen} Gleichungen und 
\textit{diophantischen} Problemen.

Wegen
\begin{gather*}
p_1(x_1,x_2,\ldots,x_n) = 0 \wedge 
\ldots
\wedge
p_k(x_1,x_2,\ldots,x_n) = 0\\
\Updownarrow\\
p_1(x_1,x_2,\ldots,x_n)^2
+ \ldots +
p_k(x_1,x_2,\ldots,x_n)^2 = 0
\end{gather*}
k\"onnte man sich auf die Frage der L\"osbarkeit einzelner
Gleichungen beschr\"anken, oft ist es aber bequemer, mit Systemen
umzugehen.

Man kann sich \"ubrigens bei der Frage nach der L\"osbarkeit
auf Gleichungen vom Grad 4 beschr\"anken --- dies sei an einem
Beispiel demonstriert: die Gleichung
\[
4 x^3y + 5z - 2 x^2 z^3 - 3 y^2 x =0
\]
ist \"aquivalent zu dem System (mit neuen Variablen $p_1, p_2, \ldots$)
von Gleichungen zweiten Grades
\begin{gather*}
p_1 = 4x, ~p_2 = p_1 x, ~p_3 = p_2 x, ~p_4 = p_3 y\\
q_1 = 5 z\\
r_1 = 2 x, ~r_2 = r_1 x, ~r_3 = r_2 z, ~r_4 = r_3 z, ~r_5 = r_4 z\\
s_1 = 3 y, ~s_2 = s_1 y, ~s_2 = s_2 x\\
p_4 + q_1 = r_5 + s_3
\end{gather*}
das sich mit obigem Trick zu einer einzigen (\"aquivalenten) Gleichung
vom Grad 4 verwandeln l\"asst.

In den beiden Extremalf\"allen:
\begin{itemize}
\item[--] alle Gleichungen sind linear (d.h. vom Grad 1), es geht
also um die ganzahligen L\"osungen eines linearen Gleichungssystems
mit ganzzahligen Koeffizienten,
\item[--] es tritt nur eine Variable auf, es geht also um
die ganzzahligen Nullstellen eines Polynoms in einer Variablen
mit ganzzahligen Koeffizienten,
\end{itemize}
kann man pr\"azise Aussagen \"uber die L\"osungen machen. 
(Stichwort im ersten Fall: euklidischer Algorithmus; im zweiten Fall
kann man aus den Koeffizienten eines Polynoms eine obere Schranke f\"ur
m\"ogliche Nullstellen berechnen und dann schlicht mittels Einsetzen
ausprobieren.

Fragen der L\"osbarkeit diophantischer Gleichungen sind von den Mathematikern
\"uber Jahrhunderte mit grossem Einsatz untersucht worden, ohne dass sich
ein einheitliches Bild ergeben h\"atte --- nur f\"ur sehr spezielle Typen
gelang es, Aussagen \"uber die L\"osbarkeit und die L\"osungen zu
gewinnen. 

Im Jahr 1900 hat der deutsche Mathematiker David \textsc{Hilbert} auf dem
Zweiten Internationalen Mathematikerkongress in Paris ein Liste von
23 Problemen ver\"offentlicht, die im 19ten Jahrhundert offengeblieben
waren und dem 20ten Jh. zur (dringenden) Bearbeitung \"ubergeben wurden.
Darunter befand sich das ber\"uhmt gewordene 10. Problem:
\begin{quote}
\it
Man entwerfe ein Verfahren, mit dessen Hilfe man in einer endlichen
Anzahl von Schritten entscheiden kann, ob eine Polynom mit 
in mehreren Variablen und mit ganzzahligen Koeffizienten eine
ganzzahlige L\"osung hat.
\end{quote}

Dieses Problem blieb lange Zeit ungel\"ost. Erst mit dem 
Berechenbarkeitstheorie in der 30er Jahren 
(\textsc{G\"odel}, \textsc{Turing}, \textsc{Church}, \textsc{Kleene})
wurden die konzeptuellen Hilfsmittel und Methoden geschaffen, um die
m\"ogliche Unl\"osbarkeit (im Sinne von Unentscheidbarkeit) 
einer solchen Problemstellung in Angriff zu nehmen. 

Wesentlich Fortschritte wurden erst in der 50er Jahren erzielt. 
Ein ganz wichtiger Durchbruch war die Arbeit
\begin{quote}
\textsc{M. Davis}, \textsc{H. Putnam}, \textsc{J. Robinson}:
\textit{The decision problem for exponential Diophantine equations},
Annals of Mathematics 74:425-436 (1961)
\end{quote}
in der gezeigt wurde, dass die Fragestellung unentscheidbar ist,
wenn man ausser Addition, Subtraktion und Multiplikation als
Basisoperationen (was zu den Polynomen f\"uhrt) auch noch die
Exponentiation als Operation zul\"asst. Was dabei eigentlich
gezeigt wurde, ist die Aussage:
\begin{quote}
\it
Jede rekursiv-aufz\"ahlbare Menge $A \subseteq \mathbb{N}^n$
ist eine exponentiell-diophantische Menge 
\end{quote}
Dabei heisst eine Menge $A \subseteq \mathbb{N}^n$
\textit{exponentiell-diophantisch}, wenn es ein \textit{Exponentialpolynom}
$f(x_1,\ldots,x_n,y_1,\ldots,y_m)$ gibt mit
\[
(a_1,\ldots,a_n) \in A \Leftrightarrow
\exists y_1 \ldots \exists y_m [\, f(a_1,\ldots,a_n,y_1,\ldots,y_m) = 0\,]
\]
Ein Exponentialpolynom wiederum ist ein Term (eine ``Funktion'',
etwas unpr\"azise gesprochen), der (die) aus ganzzahligen Konstanten und Variablen mittels Addition, Subtraktion, Multiplikation und Exponentiation aufgebaut 
wird.

Die endg\"ultige L\"osung von Hilberts 10. Problem gelang im Jahr 1970
dem damals 20-j\"ahrigen russischen Studenten Yuri \textsc{Matiyasevich}. 
Er konnte die von Davis, Putnam und Robinson noch ben\"otigte
Exponantiation elimenieren, indem er zeigte:
\begin{quote}
\it
Die dreistellige Relation $a = b^c$ ist diophantisch.
\end{quote}
Dabei heisst eine Menge  $A \subseteq \mathbb{N}^n$ 
\textit{diophantisch}, wenn, wie oben 
\[
(a_1,\ldots,a_n) \in A \Leftrightarrow
\exists y_1 \ldots \exists y_m [\, f(a_1,\ldots,a_n,y_1,\ldots,y_m) = 0\, ]
\]
wobei jetzt aber $f$ nur noch ein Polynom ist. Man kann also auch sagen:
diophantische Mengen sind diejenigen Mengen, die aus den Nullstellenmengen
eines Polynoms durch existentielle Quantifizierung (Projektion)
entstehen. Da solche Nullstellenmengen
\[
\{ (a_1,\ldots,a_n.b_1,\ldots,b_m) \in \mathbb{N}^{n+m}\,:\,
f(a_1,\ldots,a_n.b_1,\ldots,b_m) = 0 \}
\]
offensichtlich entscheidbar, also rekursiv sind, und da die
rekursiv-aufz\"ahlbaren Mengen gerade diejenigen sind, die aus den
rekursiven Mengen durch existentielle Quantifizierung entstehen,
gilt nat\"urlich:
\begin{quote}
\it
Jede diophantische Menge ist rekursiv-aufz\"ahlbar
\end{quote}
Das Resultat von \textsc{Matiyasevich} impliziert 
\begin{quote}
\it
Jede exponentiell-diophantische Menge ist diophantisch
\end{quote}
und zusammen mit dem Resultat von Davis, Putnam und Robinson
folgt
\begin{quote}
\it
Jede rekursiv-aufz\"ahlbare Menge ist diophantisch
\end{quote}
Eine unmittelbare Konsequenz ergibt sich nun aus der Existenz
rekursiv-aufz\"ahlbarer mengen, die nicht entscheidbar sind:
\begin{quote}
\it
Es kann kein Entscheidungsverfahren f\"ur Polynomgleichungen
im Sinne von Hilberts 10. Problem geben!
\end{quote}

Es ist hier nicht der Platz, auf alle Konsequenzen und Verzweigungen dieses
Resultates einzugehen. Daf\"ur gibt es eine umfangreiche Literatur, aus
der hier nur das ``authentische'' Buch
\begin{quote}
\textsc{Y. Matiyasevich}: 
\textit{Hilbert's Tenth Problem},
MIT Press 1993\\
GI mat 7.2-841
\end{quote}
hervorgehoben soll. \\
Eine f\"ur die Informatik relevante Konsequenz ist beispielsweise
die Unentscheidbarkeit der \"Aquivalenz von Funktionsausdr\"ucken, die
bereits dann eintritt, wenn man den Bereich der Polynome um so
harmlos erscheinende Funktionen wie Absolutbetrag und Sinus
erweitert. Dann wird sogar die Frage nach der Existenz \textit{reeller}
Nullstellen unentscheidbar! (\textsc{Richardson}, 1968)

Anders sieht die Situation aus, wenn man die eingangs gestellte
Frage nach der L\"osbarkeit polynomialer Gleichungen und Gleichungssysteme 
auf \textit{reelle} bzw. \textit{komplexe} L\"osungen erweitert.
Dass dies ein entscheidbares Problem ist, hat \textsc{Tarski} in
den 40er Jahren gezeigt:
\begin{quote}
\textsc{A. Tarski}: 
\textit{A Decision Method for Elementary Algebra and Geometry},
Univ. of California, 1951
\end{quote}
Sein Verfahren der ``Quantorenelimination'', das im wesentlichen auf
der klassischen Technik der ``Sturmschen Ketten'' zur 
Nullstellenbestimmung f\"ur Polynome beruht, ist allerdings extrem
ineffizient. Es hat zahlreiche Bem\"uhungen gegeben, effiziente
Verfahren zu entwickeln --- man weiss heute aber, dass das nicht m\"oglich
ist. Es gibt ``untere Schranken'' f\"ur jedes m\"oglich 
Verfahren, die super-exponentiell sind.

Als Hinweis auf die immense Schwierigkeit dieses Problems
der Untersuchung der L\"osbarkeit polynomialer Gleichungssysteme
in $\mathbb{R}$ oder $\mathbb{C}$ soll nun noch kurz dargestellt
werden, wie man das NP-vollst\"andige Problem der 3-F\"arbbarkeit von
Graphen auf dieses Polynomproblem reduzieren kann.

Ist $G=(V,E)$ ein (ungerichteter) Graph, so ordne man jedem
Knoten $v \in V$ eine Variable $x_v$ zu. Nun betrachte man das
polynomiale Gleichungssystem
\begin{eqnarray*}
x_v^3 = 1~~&~~(v \in V) \\
x_u^2 + x_u x_v + x_v^2 = 0 ~~&~~((u,v) \in E)
\end{eqnarray*}
und dessen L\"osbarkeit in $\mathbb{C}$. \\
Jede L\"osung dieses Systems muss f\"ur jeden Knoten $v$
eine ``Farbe'' $\in \{1,e^{2 \pi i /3},e^{4 \pi i /3}\}$,
also eine der dritten Einheitswurzeln ausw\"ahlen.
Die Gleichung f\"ur eine Kante $(u,v) \in E$ ist genau dann
erf\"ullt, wenn die beiden Knoten $u$ und $v$ verschiedene ``Farben''
gew\"ahlt haben.\\
Konsequenz: der Graph $G$ ist genau dann in drei Farben zul\"assig f\"arbbar,
wenn das Gleichungssystem eine L\"osung in $\mathbb{C}$ hat.
\end{document}