Quo vadis, Komplexitätstheorie

Sommerakademie Studienstiftung

Themenliste

0.

Komplexitätstheorie, was ist sie, was nützt sie?

Vortragender: E.W. Mayr (Abendvortrag, Slides).

1.

Einführung Komplexitätstheorie

Wie der Titel schon sagt, soll dieser Vortrag hauptsächlich dazu dienen, für alle Teilnehmer eine gemeinsame Grundlage und Sprache zu schaffen. Mit anderen Worten, hier geht es vor allem darum, die Standardbegriffe der Komplexitätstheorie (Turingmaschine, ${\cal P}$, ${\cal NP}$, ${\cal RP}$, etc.) zu wiederholen bzw. einzuführen und, soweit möglich, auch einen kurzen Überblick über die weiteren Vorträge zu geben.

Literatur: Lehrbücher, Kapitel 1 von [MPS98]

2.

Probabilistische Komplexitätsklassen

Die Hinzunahme von probabilistischen Aspekten hat in den letzten Jahren in der theoretischen Informatik und insbesondere auch der Komplexitätstheorie zu vielen überraschenden Resultaten geführt. Einige dieser Resultate sollen in diesem Vortrag vorgestellt werden. Einige weitere in den nächsten beiden Vorträgen.

Literatur: Kapitel 17 und 18 in [Sch95]

Vortragende: U. Brenner, M. Franz (Slides).

3.

Kryptographie und Zero-Knowledge

Kryptographische Protokolle beruhen im allgemeinen auf den folgenden beiden Annahmen (oder Varianten hiervon): ``Große'' Primzahlen können schnell erzeugt werden, das Zerlegen einer Zahl in Primfaktoren andererseits ist ``schwer''. Ziel dieses Vortrages ist es zum einen, diese vagen Aussagen zu präzisieren, zum anderen soll das weiterführende Konzept der ``Zero-Knowledge Beweise'' eingeführt und die darauf basierenden Ergebnisse vorgestellt werden.

Literatur: [Sch96], [Gol95], [GMW91]

Vortragende: M. Ebert, M. Köppe.

4.

Beweisverifikation und Nichtapproximierbarkeit

Die Entwicklung probabilistisch verifizierbarer Beweise und die Konsequenzen daraus gehören sicherlich zu den spektakulärsten Fortschritten der theoretischen Informatik in den letzten Jahren. Zu den Konsequenzen gehören insbesondere die rasanten Fortschritte bei der Klassifizierung der Approximierbarkeit kombinatorischer Optimierungsprobleme. Auf beide Aspekte soll in diesem Vortrag eingegangen werden.

Literatur: [MPS98] (insb. Kapitel 4), Kapitel 5 in [HS97]

Vortragende: T. Hübschen (Slides: ps.gz, ppt), A. Weng.

5.

Strukturen innerhalb der Klasse ${\cal P}$

Üblicherweise sieht man die Probleme der Klasse ${\cal P}$ als ``leichte'' und damit effizient lösbare Probleme an. Dies stimmt, mehr oder weniger, im Hinblick auf sequentielle Berechenbarkeit und polynomiellen Zeitbedarf. Bezüglich ihrer parallelen Berechenbarkeit und/oder der sequentiellen Berechnenbarkeit mit beschränktem Speicherplatz können sich Probleme in ${\cal P}$jedoch recht stark unterscheiden. Diesen Phänomen soll in diesem Vortrag nachgegangen werden.

Literatur: Kapitel 15 und 16 in [Pap94]

Vortragende: S. Götz, T. Tantau.

6.

10. Hilbertsches Problem

Das zehnte der berühmten 23 Probleme von Hilbert weist eine enge Verbindung zur Berechenbarkeit auf. Gefragt war hier nach einer Methode ganzzahlige Lösungen von Gleichungen der Form $f(x_1,\dots,x_n)=0$ zu bestimmen, wobei f ein Polynom mit ganzzahligen Koeffizienten ist. Seit 1970 ist das Problem gelöst, seine Lösung soll in diesem Vortrag vorgestellt werden.

Literatur: Kapitel 2 in [Sch95]

Vortragende: J. Jürjens, D. Meister.

7.

Komplexitätstheorie und Polynomideale

Polynomideale im Polynomring ${\bf Q}[x_1,\ldots,x_n]$ lassen sich darstellen als die Menge aller Polynome der Form $\sum_{i=1}^r p_i g_i$, wobei die g_i gegebene Basispolynome darstellen und die p_i den ganzen Ring ${\bf Q}[x_1,\ldots,x_n]$ durchlaufen. Solche Polynomideale stehen in engem Zusammenhang mit den sog. algebraischen Varietäten, die die Nullstellenmenge eines Systems polynomieller Gleichungen mit $x_1,\ldots,x_n$als Unbekannten darstellen. Polynomideale liefern aber auch ein Werkzeug, mit dem man (platzbeschränkte) Turingmaschinen simulieren kann, woraus sich eine ganze Reihe interessanter Folgerungen für Komplexitätsfragen in der Computeralgebra, aber auch der Petrinetz-Theorie und der Theorie der Darstellung paralleler Prozesse ergeben. Diese Zusammenhänge sollen hier vorgestellt werden.

Literatur: [May97]

Vortragende: C. Bohr (Ausarbeitung), T. Warmt (Ausarbeitung).

8.

Kolmogoroff-Komplexität

Sei x ein String über einem endlichen Alphabet. Dann bezeichnet man mit K(x), der sogenannten Kolmogoroff Komplexitzät von x, die Länge eines kürzesten Programms, das in der Lage ist, x auszugeben. In diesem Vortrag soll zunächst das Konzept der Kolmogoroff Komplexität eingeführt und erläutert werden. Im zweiten Teil des Vortrages sollen dann einige Anwendungen vorgestellt werden.

Literatur: Kapitel 8 & 9 in [Sch95], ergänzend auch [LV93]

J. Kneissler, A. Pratoussevitch.

An den beiden letzten beiden Tagen wollen wir uns mit zwei neuen, ganz anderen Ansätzen von Berechenbarkeit befassen, die zu sehr überraschenden Ergebnissen geführt haben.

9.

Biological Computing

Literatur: [Adl96] und Kapitel 8 in [HS97]
Ergänzende Literatur: [Ba], [Bb], [KMRSa], [KMRSb] und [RW95]

Vortragende: H. Fitz, U. Kühn.

10.

Quantum Computing

Literatur: Kapitel 2 in [HS97]

Vortragende: S. Brandt, J. Flötotto.