\documentclass{amsart}
\usepackage{a4,german}
\parskip 2mm
\parindent 0mm
% \setlength{\oddsidemargin}{-10mm}
% \addtolength{\textwidth}{38mm}
\addtolength{\topmargin}{10mm}
% \addtolength{\textheight}{40mm} 
% \setlength{\evensidemargin}{-10mm}
\begin{document}
\bibliographystyle{amsplain}
\begin{center}
  {\sc Erhard Aichinger}\\[4mm]
\end{center}


\title[]{{Lehrveranstaltungsank\"undigung} \\[1.5mm] 
{\Large Seminar Algebra  \\[1.5mm]
        LVA 368.151} \\[1.5mm]
  (Komplexit\"atsfragen in der universellen Algebra)}


\date{}
\maketitle

\section*{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\"urzlich haben Horv\'ath, Lawrence, M\'erai und
   Szab\'o beweisen, dass es keinen Algorithmus, dessen Laufzeit
   polynomial in der L\"ange der Terme ist, geben kann,
   der dieses Problem f\"ur die Gruppe $S_5$ l\"ost (unter der
   Annahme $P \neq NP$).
   Wir werden uns in diesem Seminar die Methoden erarbeiten,
   die man braucht, um solche Resultate zu beweisen.

\section*{NOTWENDIGE VORKENNTNISSE}
    Stoff der Lehrveranstaltungen ``Lineare Algebra'' und ``Einf\"uhrung in die Algebra und
    Diskrete Mathematik''.
    Da die Vortragsthemen unterschiedlich schwierig sind, ist das
    Seminar auch als Bakkalaureatsseminar geeignet. 

\section*{INHALT DER LEHRVERANSTALTUNG}
    \begin{itemize} 
       \item NP-vollst\"andige Probleme: Graphf\"arbung und
             Erf\"ullbarkeit BOOLEscher Formeln.
       \item Term\"aquivalenzprobleme f\"ur endliche universelle
             Algebren.
       \item Beschreibung von Term- und Polynomfunktionen
             auf universellen Algebren.
    \end{itemize}

\section*{MODUS}
   
   Alle TeilnehmerInnen w\"ahlen aus einer Liste ein Thema aus.
   Die meisten Themen sind Teile von Originalarbeiten. 
   Die Resultate sollen f\"ur einen Seminarvortrag aufbereitet
   und im Seminar vorgetragen werden.

 

\section*{TERMINE}
\textbf{Vorbesprechung: Mi, 3.10.2007, 10:30, KG 419}.

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

\section*{ANMELDUNG}
Bitte geben Sie unter {\tt http://www.kusss.jku.at} Ihre
Daten bekannt.


\end{document}



%%% Local Variables: 
%%% mode: plain-tex
%%% TeX-master: t
%%% End: 
