Erhard Aichinger

LEHRVERANSTALTUNGSANKÜNDIGUNG

SEMINAR ALGEBRA LVA 368.151

(KOMPLEXITÄTSFRAGEN IN DER UNIVERSELLEN ALGEBRA)

KURZBESCHREIBUNG

Wir werden von dem Problem ausgehen, zu bestimmen, ob zwei Terme die gleiche Funktion induzieren. Wir werden zum Beispiel fragen, ob die Terme x_{1}x_{2}^{2}x_{1}^{−1} und x_{2}^{3}x_{1}x_{2}^{−1}x_{1}^{−1} die gleiche zweistellige Funktion auf der Gruppe S_{5} induzieren.

Erst kürzlich haben Horváth, Lawrence, Mérai und Szabó beweisen, dass es keinen Algorithmus, dessen Laufzeit polynomial in der Länge der Terme ist, geben kann, der dieses Problem für die Gruppe S_{5} löst (unter der Annahme P ≠ NP). Wir werden uns in diesem Seminar die Methoden erarbeiten, die man braucht, um solche Resultate zu beweisen.

NOTWENDIGE VORKENNTNISSE

Stoff der Lehrveranstaltungen “Lineare Algebra” und “Einführung in die Algebra und Diskrete Mathematik”. Da die Vortragsthemen unterschiedlich schwierig sind, ist das Seminar auch als Bakkalaureatsseminar geeignet.

INHALT DER LEHRVERANSTALTUNG

• NP-vollständige Probleme: Graphfärbung und Erfüllbarkeit BOOLEscher Formeln.

• Termäquivalenzprobleme für endliche universelle Algebren.

• Beschreibung von Term- und Polynomfunktionen auf universellen Algebren.

MODUS

Alle TeilnehmerInnen wählen aus einer Liste ein Thema aus. Die meisten Themen sind Teile von Originalarbeiten. Die Resultate sollen für einen Seminarvortrag aufbereitet und im Seminar vorgetragen werden.

TERMINE

Vorbesprechung: Mi, 3.10.2007, 10:30, KG 419.

In der Vorbesprechung werden wir versuchen, einen gemeinsamen Termin zu finden.

ANMELDUNG

Bitte geben Sie unter http://www.kusss.jku.at Ihre Daten bekannt.