Kolloquium Sommersemester 1999
Die Dozenten der Informatik
Priv.-Doz. Dr. Peter Bürgisser, Universität Zürich
spricht über
NP-Vollständigkeit in der algebraischen Komplexitätstheorie
| Datum: | Montag, 28. Juni 1999
| | Zeit: | 17:15 Uhr
| | Ort: | Hörsaal 1, Römerstraße 164
|
ZusammenfassungDie NP-Vollständigkeit ist ein zentrales Konzept der theoretischen Informatik zur Klassifikation von Problemen nach ihrer algorithmischen Schwierigkeit. Wie Valiant erstmals gezeigt hat, läßt sich dieses Konzept auch innerhalb algebraischer Berechnungsmodelle sinnvoll formulieren. Ein anderer Zugang zu einer algebraischen Theorie der NP-Vollständigkeit wurde von Blum, Shub und Smale vorgeschlagen. Während Valiants Modell das Problem der effizienten Auswertung der Permanente zum Ausgangspunkt hat, ist das Leitproblem des letzteren Modells das Lösen von polynomialen Gleichungssystemen über den komplexen Zahlen.
Wir geben eine Übersicht über die verschiedenen Theorien der NP-Vollständigkeit und klären deren Querbeziehungen.
Um den fundamentalen Unterschied in der Komplexität von Determinante und Permanente besser zu verstehen, studieren wir eine Verallgemeinerung dieser Polynome: die sogenannten Immanenten. Die Suche nach oberen Schranken für die Komplexität dieser Polynome führt auf neue effiziente Algorithmen zur Auswertung von Darstellungen der allgemeinen linearen Gruppen.
Letzte Änderung:
16. Juni 1999, 15:27:41
|
.
Sommersemester 1999
Scholl
Klein